WEKO3
-
RootNode
アイテム
正則２部グラフに対する単純なマッチングアルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/32010
https://ipsj.ixsq.nii.ac.jp/records/32010d8f3ab31-7b67-4490-87a6-1259558b5433
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL01081004.pdf (104.3 kB)
|
Copyright (c) 2001 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| 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
× 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 | |||||||
| 収録物識別子 | 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 | |||||||
| 出版者 | 情報処理学会 | |||||||
