2006年4月
Augmenting a (k-1)-vertex-connected multigraph to an l-edge-connected and k-vertex-connected multigraph
ALGORITHMICA
- ,
- ,
- 巻
- 44
- 号
- 3
- 開始ページ
- 257
- 終了ページ
- 280
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/s00453-005-1151-4
- 出版者・発行元
- SPRINGER
For two integers k, l > 0 and an undirected multigraph G = (V, E), we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected multigraph. In this paper we show that a (k - 1)-vertex-connected multigraph G can be made l-edge-connected and k-vertex-connected by adding at most max{l + 1, 2k - 4} surplus edges over the optimum in O( min{k,root n}kn(3) + n(4)) time, where n = vertical bar V vertical bar.
- リンク情報
-
- DOI
- https://doi.org/10.1007/s00453-005-1151-4
- DBLP
- https://dblp.uni-trier.de/rec/journals/algorithmica/IshiiNI06
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000235219800005&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/algorithmica/algorithmica44.html#journals/algorithmica/IshiiNI06
- ID情報
-
- DOI : 10.1007/s00453-005-1151-4
- ISSN : 0178-4617
- DBLP ID : journals/algorithmica/IshiiNI06
- Web of Science ID : WOS:000235219800005