2026-03-13T01:26:11Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00032469 2025-01-22T16:09:19Z 1164:2592:2693:2697

グラフの多重辺付加を許さない4辺連結化問題 Simplicity - Preserving Augmentation to 4 -Edge- Connect a Graph 高藤, 大介 田岡, 智志 渡辺, 敏正 Daisuke, Takafuji Satoshi, Taoka Toshimasa, Watanabe 重みなしの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（^*，)の解決に向けての第一歩である． 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. technical report 情報処理学会 1993-05-28 application/pdf 情報処理学会研究報告アルゴリズム（AL） 48(1993-AL-033) 1993 33 40 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/32469/files/IPSJ-AL93033005.pdf jpn