@inproceedings{308188bc1021462ea7f8b392de073fca,

title = "Two-vertex connectivity augmentations for graphs with a partition constraint",

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.",

author = "Huang, {Pei Chi} and Wei, {Hsin Wen} and Chen, {Yen Chiu} and Ming-Yang Kao and Shih, {Wei Kuan} and Hsu, {Tsan Sheng}",

note = "Funding Information: Supported in part by National Science Council (Taiwan) Grants NSC 97-2221-E-001-011-MY3.; 20th International Symposium on Algorithms and Computation, ISAAC 2009 ; Conference date: 16-12-2009 Through 18-12-2009",

year = "2009",

doi = "10.1007/978-3-642-10631-6_120",

language = "English (US)",

isbn = "3642106307",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "1195--1204",

booktitle = "Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings",

}