WEKO3
アイテム
グラフの多重辺付加を許さない4辺連結化問題
https://ipsj.ixsq.nii.ac.jp/records/32428
https://ipsj.ixsq.nii.ac.jp/records/324282839a0a2-5339-4707-930f-fbf464454ece
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1994 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1994-03-17 | |||||||
タイトル | ||||||||
タイトル | グラフの多重辺付加を許さない4辺連結化問題 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | The 4 -edge- connectivity augmentation problem without adding multiple edges | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
広島大学工学部第二類(電気系) | ||||||||
著者所属 | ||||||||
広島大学工学部第二類(電気系) | ||||||||
著者所属 | ||||||||
広島大学工学部第二類(電気系) | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Circuits and Systems, Faculty of Engineering, Hiroshima Watanabe | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Circuits and Systems, Faculty of Engineering, Hiroshima Watanabe | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Circuits and Systems, Faculty of Engineering, Hiroshima Watanabe | ||||||||
著者名 |
高藤, 大介
× 高藤, 大介
|
|||||||
著者名(英) |
Daisuke, Takafuji
× Daisuke, Takafuji
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 重みなしのk辺連結化問題(?kECAと略記)とは,与えられた無向グラフG:(,)に付加して得られるグラフG'=(,A∪A')がk辺連結となるような最小辺集合A'を求める問題である.G,G'共に単純グラフとしたUW?kECAをUW?kECA(,)と表し,Gは多重グラフでもよいがG'構成時に多重辺の追加は許さない場合をUW?kECA(^*,)と表す,本稿では与えられたグラフの辺連結度ec()=2の場合のUW?4ECA(,)にするO(|N|^2+|A|)時間のアルゴリズムを提案する.本結果は未解決問題である一般的なUW?kECA(^*,)の解決に向けての第一歩である. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The unweighted k-edge-connectivity augmentation problem (W-kECA for shor)is defined by "Given a graph G = (N,A), find an edge set A' of minimum cardinality, with each edge connecting distinct vertices of N, such that G' = (N,A∪A') is k-edge-connected." Our subject is UW-4ECA(S,SA) for λ = 2, where both G and G' are simple in UW-kECA(S,SA). We propose an O(|N|^2+|A|) algorithm for solving UW-4ECA(S,SA) where G is 2-edge-connected, simple and |N|〓5. The result is a first step toward an open problem UW-kECA(^*,SA). | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 1994, 号 26(1993-AL-038), p. 25-32, 発行日 1994-03-17 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |