2024-03-29T09:44:07Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000322402023-04-27T10:00:04Z01164:02592:02666:02670
辺連結度,点連結度を同時に最適増大させる問題Augmenting Edge - Connectivity and Vertex - Connectivity Simultaneously in Undirected Graphsjpnhttp://id.nii.ac.jp/1001/00032240/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32240&item_no=1&attribute_id=1&file_no=1Copyright (c) 1997 by the Information Processing Society of Japan京都大学工学研究科数理工学教室京都大学工学研究科数理工学教室京都大学工学研究科数理工学教室石井, 利昌永持仁茨木, 俊秀辺連結度,点連結度を同時に最適増大させる問題とは,入力として,無向多重グラフG=(,)と,要求関数{γ_λ(,)∈Z^+|x,y∈V},{γ_κ(,)∈Z^+|x,y∈V}(^+は非負整数集合を表す)が与えられたとき,最小本数の辺をGに加えることで,全てのx,y∈V間の辺連結度および点連結度をそれぞれγ_λ(,)以上,かつγ_κ(,)以上にする問題である.本研究では,全てのx,y∈Vについてγ_κ(,)=2である場合については,この問題が多項式時間で解けることを示す.Given an undirected multigraph G=(V,E) and requirement functions {γ_λ(x,y)∈Z^+|x,y∈V} and {γ_κ(x,y)∈Z^+|x,y∈V} (where Z^+ is the set of nonnegative integers), the edge and vertex-connectivities augmentation problem asks to augment G by adding the smallest number of new edges to G so that for very x,y∈V, the edge-connectivity and vertex-connectivity between x and y are at least γ_λ(x,y) and γ_κ(x,y), respectively in the resulting graph G'. In this paper, we show that if γ_κ(x,y)=2 holds for every x,y∈V, then the problem can be solved in polynomial time.AN1009593X情報処理学会研究報告アルゴリズム(AL)199726(1996-AL-056)41481997-03-142009-06-30