Source location problems considering vertex-connectivity and edge-connectivity simultaneously

Autor: Mitsuo Yokoyama, Motoyasu Ito, Hideyuki Uehara, Hiro Ito, Yuichiro Itatsu, Kazuhiro Nakai
Rok vydání: 2002
Předmět:
Zdroj: Networks. 40:63-70
ISSN: 1097-0037
0028-3045
DOI: 10.1002/net.10034
Popis: Let G = (V, E) be an undirected multigraph, where V and E are a set of vertices and a set of edges, respectively. Let k and l be fixed nonnegative integers. This paper considers location problems of finding a minimum-size vertex-subset S ⊆ V such that for each vertex x ∈ V the vertex-connectivity between S and x is greater than or equal to k and the edge-connectivity between S and x is greater than or equal to l. For the problem with edge-connectivity requirements, that is, k = 0, an O(L(|V|, |E|, l)) time algorithm is already known, where L(|V|, |E|, l) is the time to find all h-edge-connected components for h = 1, 2, … , l and O(L(|V|, |E|, l)) = O(|E| + |V|2 + |V|min{|E|, l|V|}min{l, |V|}) is known. In this paper, we show that the problem with k ≥ 3 is NP-hard even for l = 0. We then present an O(L(|V|, |E|, l)) time algorithm for 0 ≤ k ≤ 2 and l ≥ 0. Moreover, we prove that the problem parameterized by the size of S is fixed-parameter tractable (FPT) for k = 3 and l ≥ 0. © 2002 Wiley Periodicals, Inc.
Databáze: OpenAIRE
Externí odkaz: