論文

査読有り
1997年

Augmenting edge and vertex connectivities simultaneously

ALGORITHMS AND COMPUTATION, PROCEEDINGS
  • Toshimasa, I
  • ,
  • H Nagamochi
  • ,
  • Toshihide, I

1350
開始ページ
102
終了ページ
111
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1007/3-540-63890-3_12
出版者・発行元
SPRINGER-VERLAG BERLIN

Given an undirected multigraph G = (V, E) and requirement functions r(lambda) : ((V)(2)) --> Z(+) and r(kappa) : ((V)(2)) --> Z(+) (where Z(+) is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the edge-connectivity and vertex-connectivity between every pair x,y is an element of V become at least r(lambda)(x,y) and r(kappa)(x,y), respectively, in the resulting graph G '. In this paper, we show that the problem can be solved in polynomial time if r(kappa) is given by r(kappa)(x,y) = 2 for all x,y is an element of V.

リンク情報
DOI
https://doi.org/10.1007/3-540-63890-3_12
DBLP
https://dblp.uni-trier.de/rec/conf/isaac/IshiiNI97
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902174874434299
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000170662700012&DestApp=WOS_CPL
URL
http://dblp.uni-trier.de/db/conf/isaac/isaac97.html#conf/isaac/IshiiNI97
ID情報
  • DOI : 10.1007/3-540-63890-3_12
  • ISSN : 0302-9743
  • DBLP ID : conf/isaac/IshiiNI97
  • J-Global ID : 200902174874434299
  • Web of Science ID : WOS:000170662700012

エクスポート
BibTeX RIS