WEKO3
アイテム
グラフの多重辺付加を許さない4辺連結化問題
https://ipsj.ixsq.nii.ac.jp/records/32469
https://ipsj.ixsq.nii.ac.jp/records/32469db3b7c41-ac09-44a6-bd47-cfc8ba2dad4e
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1993 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1993-05-28 | |||||||
タイトル | ||||||||
タイトル | グラフの多重辺付加を許さない4辺連結化問題 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Simplicity - Preserving Augmentation to 4 -Edge- Connect a Graph | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
広島大学工学部第二類回路システム工学講座 | ||||||||
著者所属 | ||||||||
広島大学工学部第二類回路システム工学講座 | ||||||||
著者所属 | ||||||||
広島大学工学部第二類回路システム工学講座 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Circuits and Systems, Faculty of Engineering, Hiroshima University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Circuits and Systems, Faculty of Engineering, Hiroshima University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Circuits and Systems, Faculty of Engineering, Hiroshima University | ||||||||
著者名 |
高藤, 大介
× 高藤, 大介
|
|||||||
著者名(英) |
Daisuke, Takafuji
× Daisuke, Takafuji
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 重みなしのk辺連結化問題((?4ECAと略記)とは,与えられた無向グラフG=(,)に付加すれば得られるグラフG'=(,A∪A')がk辺連結となるような最小辺集合A'を求める問題である.G,G'共に単純グラフとしたUW?4ECAをUW?4ECA(,)と表し,Gは多重グラフでもよいがG'構成時の多重辺付加は許さない場合をUW?4ECA(^*,)と表す.本稿ではUW?4ECA(,)に対するO(|N|^)アルゴリズムを提案する.これはUW?4ECA(^*,)にも応用できる.また,葉グラフと呼ばれるグラフの最大マッチングの辺数も示している.本結果は未解決問題である一般的なUW?kECA(^*,)の解決に向けての第一歩である. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The unweighted k-edge-connectivity augmentation problem (UW-kECA) is defined by "Given a graph G=(N,A), find an edge set A' of minimum cardinality, with each element connecting distinct vertices of N, such that G'=N,A∪A') is k-edge-connected." Let UW-4ECA(S,SA) denote UW-kECA such that both G and G' are simple. The paper proposes an O(|N|^2) algorithm for solving UW-4ECA(S,SA). The result can be used in solving UW-4ECA(^*,SA) in which G may have multiple edges and creation of new multiple edges in constructing G' is not allowed. Also presented is the cardinality of a maximum matching of a leaf graph that is constructed from G, and the results may be interesting from viewpoint of combinatorial theory. The paper is a first step toward an open problem UW-kECA(^*,SA) for general k〓4. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 1993, 号 48(1993-AL-033), p. 33-40, 発行日 1993-05-28 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |