2007年3月
Minimum cost source location problem with local 3-vertex-connectivity requirements
THEORETICAL COMPUTER SCIENCE
- ,
- ,
- 巻
- 372
- 号
- 1
- 開始ページ
- 81
- 終了ページ
- 93
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.tcs.2006.11.010
- 出版者・発行元
- ELSEVIER SCIENCE BV
Let G = (V, E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v E V has a demand d(V) epsilon Z(+) and a cost c(v) epsilon R+, where Z(+) and R+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G requires finding a set S of vertices minimizing Sigma(v epsilon S) c(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v epsilon V - S. It is known that if there exists a vertex v epsilon V with d(v) >= 4, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(vertical bar V vertical bar(4) log(2) vertical bar V vertical bar) time if d(v) <= 3 holds for each vertex v epsilon V. (c) 2006 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.tcs.2006.11.010
- ISSN : 0304-3975
- CiNii Articles ID : 120000802939
- Web of Science ID : WOS:000244999600007