正則２部グラフに対する単純なマッチングアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2001-11-27
• タイトル: 正則２部グラフに対する単純なマッチングアルゴリズム
• タイトル / 言語: en
• タイトル: A Simple Matching Algorithm for Regular Bipartite Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院基礎工学研究科システム科学分野
• 著者所属: 大阪大学大学院基礎工学研究科システム科学分野
• 著者所属: 大阪大学大学院基礎工学研究科システム科学分野
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science, Osaka University,
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science, Osaka University,
• 著者所属(英): en
• 著者所属(英): Division of Systems Science, Graduate School of Engineering Science, Osaka University,
• 著者名: 牧野, 和久; 高畑, 貴志; 藤重, 悟
• 著者名(英): Kazuhisa, Makino; Takashi, Takabatake; Satoru, Fujishige
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，△-正則２ 部グラフに対する完全マッチング問題を考察する．ただし，グラフG は，n 節点，m 枝，すなわち，1/2 n △=m とする．我々は，まず，Gabow の方法に基づく新しい単純なO(m log n )アルゴリズムを与える．次に，Cole とHopcroft が提案した正則２ 部グラフに対する辺疎化手法を取り入れることにより，そのアルゴリズムをO(m +n log n log △)に改善する．我々のアルゴリズムは，動的木やスプレイ木などの高度なデータ構造を必要としない．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2001, 号 115(2001-AL-081), p. 27-34, 発行日 2001-11-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会