3 0 0 0 OA 正則2部グラフに対する単純なマッチングアルゴリズム
- 著者
- 牧野 和久 高畑 貴志 藤重 悟
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL)
- 巻号頁・発行日
- vol.2001, no.115(2001-AL-081), pp.27-34, 2001-11-27
本論文では,△-正則2 部グラフに対する完全マッチング問題を考察する.ただし,グラフG は,n 節点,m 枝,すなわち,1/2 n △=m とする.我々は,まず,Gabow の方法に基づく新しい単純なO(m log n )アルゴリズムを与える.次に,Cole とHopcroft が提案した正則2 部グラフに対する辺疎化手法を取り入れることにより,そのアルゴリズムをO(m +n log n log △)に改善する.我々のアルゴリズムは,動的木やスプレイ木などの高度なデータ構造を必要としない.
3 0 0 0 OA 守備特訓に喘ぐ外野手のための捕球経路問題 (計算機科学基礎理論の新展開)
- 著者
- 佐久間 俊慎 小野 廣隆 山下 雅史 朝廣 雄一 牧野 和久 堀山 貴史
- 出版者
- 京都大学数理解析研究所
- 雑誌
- 数理解析研究所講究録 (ISSN:18802818)
- 巻号頁・発行日
- vol.1325, pp.8-14, 2003-05
1 0 0 0 複基多面体:台の大きさが2以下の辺ベクトルを有する多面体の構造
- 著者
- 藤重 悟 牧野 和久 高畑 貴志 柏原 賢二
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
- 巻号頁・発行日
- vol.2001, no.7, pp.51-58, 2001-01-19
各辺ベクトルの台の大きさが2以下である多面体のクラスについて考える.このような凸多面体を複基多面体と呼び,頂点をもつ任意の多面体P⊆R^Vについて,次の3つが等価であることを示す.(1) Pが複基多面体である.(2) 台Vの法線ベクトルをもつPの各面は,ある基多面体の反転および軸方向のスケーリングによって得られる.(3) Pの支持関数は,R^Vの各象限上の劣モジュラ関数である.We consider a class of pointed convex polyhedra in R^V whose edge vectors have the support of size at most 2. We call such a convex polyhedron a polybasic polyhedron and show that for a pointed polyhedron P ⊆ R^V the following three statements are equivalent: (1) P is a polybasic polyhedron. (2) Each face of P with a normal vector of the full support V is obtained from a base polyhedron by a reflection and scalings along axes. (3) The support function of P is a submodular function on each orthant of R^V.
1 0 0 0 OA 劣モジュラ的構造に基づく離散最適化基礎理論の展開と高速アルゴリズム開発
大規模離散最適化問題の有する劣モジュラ的な離散構造に注目し, 効率的なアルゴリズムの構築のために有効な離散構造を研究した.個別には,ネットワーク・フロー, マッチング,多品種フロー, 施設配置問題, 資源配分問題, グラフ連結度,通信網設計,待ち行列ネットワークに関わる離散構造,双対貪欲アルゴリズムに関わる離散構造(双対貪欲多面体, ゾノトープ) ,ホーン論理関数や安定マッチングの離散凸構造,などであり,個別の劣モジュラ的な離散構造の解明に基づき,それらの知見を横断的に総合する基礎理論の構築と高速アルゴリズムの開発を行った.