Location Problems Based on Node-Connectivity and Edge-Connectivity between Nodes and Node-Subsets

摘要

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 is contaioed in 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 0(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).