@techreport{oai:ipsj.ixsq.nii.ac.jp:00032010,
 author = {牧野, 和久 and 高畑, 貴志 and 藤重, 悟 and Kazuhisa, Makino and Takashi, Takabatake and Satoru, Fujishige},
 issue = {115(2001-AL-081)},
 month = {Nov},
 note = {本論文では，△-正則２ 部グラフに対する完全マッチング問題を考察する．ただし，グラフG は，n 節点，m 枝，すなわち，1/2 n △=m とする．我々は，まず，Gabow の方法に基づく新しい単純なO(m log n )アルゴリズムを与える．次に，Cole とHopcroft が提案した正則２ 部グラフに対する辺疎化手法を取り入れることにより，そのアルゴリズムをO(m +n log n log △)に改善する．我々のアルゴリズムは，動的木やスプレイ木などの高度なデータ構造を必要としない．, We consider the perfect matching problem for a △-regular bipartite graph with n vertices and m edges,i.e.,1/2n△=m .We first give a new simple O(m log n )algorithm based on Gabow ’s approach, and then improve it to a faster O(m+n log n log △)algorithm by incorporating Cole and Hopcroft's edge-sparsification for regular bipartite graphs. Our algorithms employ no sophisticated data structure such as dynamic tree and splay tree.},
 title = {正則２部グラフに対する単純なマッチングアルゴリズム},
 year = {2001}
}