@techreport{oai:ipsj.ixsq.nii.ac.jp:00032469,
 author = {高藤, 大介 and 田岡, 智志 and 渡辺, 敏正 and Daisuke, Takafuji and Satoshi, Taoka and Toshimasa, Watanabe},
 issue = {48(1993-AL-033)},
 month = {May},
 note = {重みなしの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.},
 title = {グラフの多重辺付加を許さない4辺連結化問題},
 year = {1993}
}