Paper Info
Title
On the Minimum Augmentation of an l-Connected Graph to a k-Connected Graph
Abstract
Given an undirected graph G = (V, E) and a positive integer k, we consider the problem of augmenting G by the smallest number of new edges to obtain a k-vertex-connected graph. In this paper, we show that, for k ≥ 4 and k ≥ l+2, an l-vertex-connected graph G can be made k-vertex-connected by adding at most δ(k-1)+max{0, (δ-1)(l-3)-1} surplus edges over the optimum in O(δ(k2n2 + k3n3/2)) time, where δ = k - l and n = |V|.
Year
DOI
Venue
2000
10.1007/3-540-44985-X_26
SWAT
Keywords
Field
DocType
new edge,l-connected graph,surplus edge,k-vertex-connected graph,k-connected graph,undirected graph,minimum augmentation,augmenting g,smallest number,l-vertex-connected graph,positive integer k,connected graph
Integer,Graph theory,Discrete mathematics,Graph,Combinatorics,Bound graph,Degree (graph theory),Distance-regular graph,Connectivity,Time complexity,Mathematics
Conference
Volume
ISSN
ISBN
1851
0302-9743
3-540-67690-2
Citations 
PageRank 
References 
6
0.49
12
Authors
2
Name
Order
Citations
PageRank
Toshimasa Ishii111017.03
Hiroshi Nagamochi21513174.40