Paper Info
Title
Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
Abstract
Given an undirected multigraph G = (V, E), a family W of sets W ⊆ V of vertices (areas), and a requirement function r : W → Z+ (where Z+ is the set of nonnegative integers) we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least r(W) edge-disjoint paths between v and W for every pair of a vertex v ∈ V and an area W ∈ W. So far this problem was shown to be NP-hard in the uniform case of r(W) = 1 for each W ∈ W, and polynomially solvable in the uniform case of r(W) = r ≥ 2 for each W ∈ W. In this paper, we show that the problem can be solved in O(m + pn4(r* + logn)) time, even if r(W) ≥ 2 holds for each W ∈ W, where n = |V|, m = |{{u, v}|(u, v) ∈ E}|, p = |W|, and r* = max{r(W)|W ∈ W}.
Year
DOI
Venue
2006
10.1016/j.dam.2006.04.017
Discrete Applied Mathematics
Keywords
Field
DocType
vertex subsets,polynomially solvable,sets w,undirected graph,minimum augmentation,node-to-area connectivity,polynomial time deterministic algorithm,area w,local edge-connectivity,vertex v,new edge,uniform case,family w,connectivity augmentation problem,nonnegative integer,augmenting g,edge-disjoint path,graph connectivity,polynomial time
Integer,Graph,Discrete mathematics,Combinatorics,Multigraph,Vertex (geometry),Vertex (graph theory),Connectivity,Mathematics
Journal
Volume
Issue
ISSN
154
16
Discrete Applied Mathematics
Citations 
PageRank 
References 
10
1.20
7
Authors
2
Name
Order
Citations
PageRank
Toshimasa Ishii111017.03
Masayuki Hagiwara2121.94