グラフの多重辺付加を許さない4辺連結化問題

• 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; Satoshi, Taoka; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: 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
• 書誌レコードID / 収録物識別子: 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
• 出版者: 情報処理学会