Paper Info
Title
Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint (Extended Abstract)
Abstract
In this paper, we study the two-vertex connectivity augmentation problem in an undirected graph whose vertices are partitioned into k sets. Our objective is to add the smallest number of edges to the graph such that the resulting graph is 2-vertex connected under the constraint that each new edge is between two different sets in the partition. We propose an algorithm to solve the above augmentation problem that runs in linear time in the size of the input graph.
Year
DOI
Venue
2009
10.1007/978-3-642-10631-6_120
ISAAC
Keywords
Field
DocType
new edge,different set,extended abstract,k set,undirected graph,two-vertex connectivity augmentations,linear time,resulting graph,smallest number,two-vertex connectivity augmentation problem,partition constraint,augmentation problem,input graph,difference set
Discrete mathematics,Strength of a graph,Combinatorics,Line graph,Loop (graph theory),Computer science,Vertex (graph theory),Cycle graph,Graph partition,Windmill graph,Butterfly graph
Conference
Volume
ISSN
Citations 
5878
0302-9743
0
PageRank 
References 
Authors
0.34
11
6
Name
Order
Citations
PageRank
Pei-Chi Huang1649.92
Hsin-Wen Wei222230.39
Yen-Chiu Chen3405.64
Ming-Yang Kao41520159.74
Wei-Kuan Shih593898.21
Tsan-sheng Hsu6737101.00