Paper Info
Title
Location Problems Based on Node-Connectivity and Edge-Connectivity between Nodes and Node-Subsets
Abstract
Let G = (V, E) be an undirected multi-graph where V and E are a set of nodes and a set of edges, respectively. Let k and l be fixed nonnegative integers. This paper considers location problems of finding a minimum size of node-subset S ⊆ V such that node-connectivity between S and x is greater than or equal to k and edge-connectivity between S and x is greater than or equal to l for every x ∈ V . This problem has important applications for multi-media network control and design. For a problem of considering only edge-connectivity, i.e., k = 0, an O(L(|V|, |E|, l)) = O(|E| + |V|2 + |V|min{|E|, l|V|}min{l, |V|}) time algorithm was already known, where L(|V|, |E|, l) is a time to find all h-edge-connected components for h = 1, 2, ..., l. This paper presents an O(L(|V|, |E|, l)) time algorithm for 0 ≤ k ≤ 2 and l ≥ 0. It also shows that if k ≥ 3, the problem is NP-hard even for l = 0. Moreover, it shows that if the size of S is regarded as a parameter, the parameterized problem for k = 3 and l ≤ 1 is FPT (fixed parameter tractable).
Year
DOI
Venue
2000
10.1007/3-540-40996-3_29
ISAAC
Keywords
Field
DocType
undirected multi-graph,important application,minimum size,location problem,fixed parameter tractable,h-edge-connected component,time algorithm,nonnegative integer,multi-media network control,parameterized problem
Integer,Data structure,Discrete mathematics,Combinatorics,Parameterized complexity,Combinatorial optimization,Network control,Connectivity,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-41255-7
5
0.68
References 
Authors
3
5
Name
Order
Citations
PageRank
Hiro Ito129039.95
Yuichiro Itatsu2262.31
Hideyuki Uehara35412.14
Mitsuo Yokoyama4669.51
Motoyasu Ito5141.36