著者

牧野 和久 高畑 貴志 藤重 悟

雑誌

情報処理学会研究報告アルゴリズム(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 △)に改善する.我々のアルゴリズムは,動的木やスプレイ木などの高度なデータ構造を必要としない.

著者

藤重 悟 牧野 和久 高畑 貴志 柏原 賢二

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(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.