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 △)に改善する.我々のアルゴリズムは,動的木やスプレイ木などの高度なデータ構造を必要としない.
言及状況
Twitter (3 users, 3 posts, 5 favorites)
k-正則二部グラフの完全マッチングO(m log n)：
https://t.co/oQSMMgDNrb
まずk=2^tだとすると、オイラー路を取って奇数番目の辺だけを残すっていうのを繰り返せばO(m)で完全マッチングが見つかる（Gabowのアルゴリズム）