Minimum cost source location problem with local 3-vertex-connectivity requirements |
| |
Authors: | Toshimasa Ishii Hitoshi Fujita Hiroshi Nagamochi |
| |
Affiliation: | 1. Department of Information and Management Science, Otaru University of Commerce, Otaru-city Hokkaido 047-8501, Japan;2. Matsushita Systems and Technology Co., Ltd., Osaka 540-6321, Japan;3. Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan |
| |
Abstract: | Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has a demand d(v)∈Z+ and a cost c(v)∈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 ∑v∈Sc(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v∈V−S. It is known that if there exists a vertex v∈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(|V|4log2|V|) time if d(v)≤3 holds for each vertex v∈V. |
| |
Keywords: | Graph algorithm Undirected graph Location problem Local vertex-connectivity Polynomial time algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|