Two-vertex connectivity augmentations for graphs with a partition constraint

Pei Chi Huang; Hsin Wen Wei; Yen Chiu Chen; Ming-Yang Kao; Wei Kuan Shih; Tsan Sheng Hsu

doi:10.1007/978-3-642-10631-6_120

Two-vertex connectivity augmentations for graphs with a partition constraint

Pei Chi Huang^*, Hsin Wen Wei, Yen Chiu Chen, Ming-Yang Kao, Wei Kuan Shih, Tsan Sheng Hsu

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
Pages	1195-1204
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-10631-6_120
State	Published - 2009
Event	20th International Symposium on Algorithms and Computation, ISAAC 2009 - Honolulu, HI, United States Duration: Dec 16 2009 → Dec 18 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5878 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	20th International Symposium on Algorithms and Computation, ISAAC 2009
Country/Territory	United States
City	Honolulu, HI
Period	12/16/09 → 12/18/09

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-10631-6_120

Cite this

Huang, P. C., Wei, H. W., Chen, Y. C., Kao, M-Y., Shih, W. K., & Hsu, T. S. (2009). Two-vertex connectivity augmentations for graphs with a partition constraint. In Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings (pp. 1195-1204). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5878 LNCS). https://doi.org/10.1007/978-3-642-10631-6_120

Huang, Pei Chi ; Wei, Hsin Wen ; Chen, Yen Chiu et al. / Two-vertex connectivity augmentations for graphs with a partition constraint. Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. 2009. pp. 1195-1204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

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

}

Huang, PC, Wei, HW, Chen, YC, Kao, M-Y, Shih, WK & Hsu, TS 2009, Two-vertex connectivity augmentations for graphs with a partition constraint. in Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5878 LNCS, pp. 1195-1204, 20th International Symposium on Algorithms and Computation, ISAAC 2009, Honolulu, HI, United States, 12/16/09. https://doi.org/10.1007/978-3-642-10631-6_120

Two-vertex connectivity augmentations for graphs with a partition constraint. / Huang, Pei Chi; Wei, Hsin Wen; Chen, Yen Chiu et al.
Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. 2009. p. 1195-1204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5878 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Two-vertex connectivity augmentations for graphs with a partition constraint

AU - Huang, Pei Chi

AU - Wei, Hsin Wen

AU - Chen, Yen Chiu

AU - Kao, Ming-Yang

AU - Shih, Wei Kuan

AU - Hsu, Tsan Sheng

N1 - Funding Information: Supported in part by National Science Council (Taiwan) Grants NSC 97-2221-E-001-011-MY3.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=75649116497&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=75649116497&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-10631-6_120

DO - 10.1007/978-3-642-10631-6_120

M3 - Conference contribution

AN - SCOPUS:75649116497

SN - 3642106307

SN - 9783642106309

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1195

EP - 1204

BT - Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings

T2 - 20th International Symposium on Algorithms and Computation, ISAAC 2009

Y2 - 16 December 2009 through 18 December 2009

ER -

Huang PC, Wei HW, Chen YC, Kao M-Y, Shih WK, Hsu TS. Two-vertex connectivity augmentations for graphs with a partition constraint. In Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. 2009. p. 1195-1204. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-10631-6_120

Two-vertex connectivity augmentations for graphs with a partition constraint

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this