Premium
Source location problems considering vertex‐connectivity and edge‐connectivity simultaneously
Author(s) -
Ito Hiro,
Ito Motoyasu,
Itatsu Yuichiro,
Nakai Kazuhiro,
Uehara Hideyuki,
Yokoyama Mitsuo
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10034
Subject(s) - combinatorics , vertex (graph theory) , multigraph , vertex connectivity , parameterized complexity , mathematics , undirected graph , graph , discrete mathematics
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.