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

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationAlgorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
Pages1195-1204
Number of pages10
DOIs
StatePublished - Dec 1 2009
Event20th International Symposium on Algorithms and Computation, ISAAC 2009 - Honolulu, HI, United States
Duration: Dec 16 2009Dec 18 2009

Publication series

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

Other

Other20th International Symposium on Algorithms and Computation, ISAAC 2009
CountryUnited States
CityHonolulu, HI
Period12/16/0912/18/09

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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