論文

査読有り
2016年11月

The minimum vulnerability problem on specific graph classes

JOURNAL OF COMBINATORIAL OPTIMIZATION
  • Yusuke Aoki
  • ,
  • Bjarni V. Halldorsson
  • ,
  • Magnus M. Halldorsson
  • ,
  • Takehiro Ito
  • ,
  • Christian Konrad
  • ,
  • Xiao Zhou

32
4
開始ページ
1288
終了ページ
1304
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1007/s10878-015-9950-2
出版者・発行元
SPRINGER

Suppose that each edge e of an undirected graph G is associated with three nonnegative integers , and , called the cost, vulnerability and capacity of e, respectively. Then, we consider the problem of finding paths in G between two prescribed vertices with the minimum total cost; each edge e can be shared without any cost by at most paths, and can be shared by more than paths if we pay , but cannot be shared by more than paths even if we pay the cost for e. This problem generalizes the disjoint path problem, the minimum shared edges problem and the minimum edge cost flow problem for undirected graphs, and it is known to be NP-hard. In this paper, we study the problem from the viewpoint of specific graph classes, and give three results. We first show that the problem is NP-hard even for bipartite outerplanar graphs, 2-trees, graphs with pathwidth two, complete bipartite graphs, and complete graphs. We then give a pseudo-polynomial-time algorithm for bounded treewidth graphs. Finally, we give a fixed-parameter algorithm for chordal graphs when parameterized by the number of required paths.

リンク情報
DOI
https://doi.org/10.1007/s10878-015-9950-2
DBLP
https://dblp.uni-trier.de/rec/journals/jco/AokiHHIKZ16
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000387107700018&DestApp=WOS_CPL
URL
http://dblp.uni-trier.de/db/journals/jco/jco32.html#journals/jco/AokiHHIKZ16
Scopus
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84941341654&origin=inward
Scopus Citedby
https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=84941341654&origin=inward
ID情報
  • DOI : 10.1007/s10878-015-9950-2
  • ISSN : 1382-6905
  • eISSN : 1573-2886
  • DBLP ID : journals/jco/AokiHHIKZ16
  • SCOPUS ID : 84941341654
  • Web of Science ID : WOS:000387107700018

エクスポート
BibTeX RIS