WEKO3
アイテム
無向グラフ上の辺分離問題を解く簡単なÕ（mn）時間アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/32259
https://ipsj.ixsq.nii.ac.jp/records/322592bf20980-490b-4672-a94a-c99a455089e1
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL96054006.pdf (743.1 kB)
|
Copyright (c) 1996 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1996-10-17 | |||||||
| タイトル | ||||||||
| タイトル | 無向グラフ上の辺分離問題を解く簡単なÕ（mn）時間アルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A Simple Õ (nm) Time Edge - Splitting Algorithm in Undirected Graphs | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 京都大学工学研究科数理工学教室 | ||||||||
| 著者所属 | ||||||||
| 京都大学工学研究科数理工学教室 | ||||||||
| 著者所属 | ||||||||
| 京都大学工学研究科数理工学教室 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Applied Mathematics and Physics Graduate School of Engineering Kyoto University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Applied Mathematics and Physics Graduate School of Engineering Kyoto University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Applied Mathematics and Physics Graduate School of Engineering Kyoto University | ||||||||
| 著者名 |
永持仁
× 永持仁
|
|||||||
| 著者名(英) |
Hiroshi, Nagamochi
× Hiroshi, Nagamochi
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 偶数次数の指定された点sを持つk?辺連結無向多重グラフG=(，)が与えられたとき，sに接続する2辺(，)，(，υ）を1辺(，υ）に置き換える操作を反復し（グラフのk?辺連結性を保ちながら）sを孤立点化させる問題を考える。最近、n=|V|，mをGにおいて辺の張られている点対の数としたとき、この問題を解くO((+n log )log )時間のアルゴリズムが開発されたが[H．Nagamochi and T．Ibaraki，Deterministic O^^?() time edge?splitting in undirected graphs，Proceedings 28th ACM Symposium on Theory of Computing，1996，pp．64?73]、このアルゴリズムはやや複雑である。本報告では、同じO((+n log )log )の計算時間を持つより簡単なアルゴリズムを提案する。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | This paper presents a deterministic O(n(m+n log n)log n) = O^^縲鰀(nm) time algorithm for splitting off all edges incident to a vertex s of even degree in a multigraph G, where n is the number of vertices in G and and m is the number of vertex pairs between which G has an edge. The algorithm is much simpler than the previous O(n(m+n log n)log n) time edge-splitting algorithm due to [H.Nagamochi and T.Ibaraki, Deterministic O^^縲鰀(nm) time edge-splitting in undirected graphs, Proceedings 28th ACM Symposium on Theory of Computing, 1996, pp.64-73]. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1996, 号 100(1996-AL-054), p. 41-48, 発行日 1996-10-17 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
