2024-03-29T20:26:59Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000322622024-03-29T05:26:34Z01164:02592:02672:02673
複数の指定点集合に対する2辺?及び2点-連結化問題の解法Solving the 2 -Edge- or 2 -Vertex- Connectivity Augmentation Problem for Specified Sets of Verticesjpnhttp://id.nii.ac.jp/1001/00032262/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32262&item_no=1&attribute_id=1&file_no=1Copyright (c) 1996 by the Information Processing Society of Japan広島大学工学部第二類(電気系)回路システム工学大講座広島大学工学部第二類(電気系)回路システム工学大講座広島大学工学部第二類(電気系)回路システム工学大講座土屋, 憲蔵間島, 利也渡邉, 敏正指定点集合族に対する2辺連結化問題(ECA?nS)(点連結化問題(VCA?nS))とは,無向グラフG=(,)と指定点集合族Ψ={S_i⊆V|S_i|〓2,i=1,…,n}が与えられたときに,Gに辺を付加すると,各S_i(=1,…,)中の任意の2点間に辺素(内素)な道が2本以上存在するグラフとなるような,付加すべき最小の辺集合を求める問題である.本稿では,2ECA?nSV及び2VCA?nSVに対する解法を示す.The 2-edge(vertex)-connectivity augmentation problem for specified sets of vertices, 2ECA-nSV (2VCA-nSV), is defined as follows: given an undirected graph G = (V,E) and specified sets of vertices S_i⊆V(|S_i|〓2,i=1,…,n), find a smallest set of edges to be added to G so that resulting graph has at least two edge-disjoint (internally disjoint) paths between any pair of vertices in S_i for each i,i=1,…,n. This paper proposes two algorithms: one for solving 2ECA-nSV; the other for solving 2VCA-nSV.AN1009593X情報処理学会研究報告アルゴリズム(AL)1996100(1996-AL-054)65721996-10-172009-06-30