### 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 | |

State | Published - Dec 1 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 | United States |

City | Honolulu, HI |

Period | 12/16/09 → 12/18/09 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*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

}

*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; Kao, Ming-Yang; Shih, Wei Kuan; Hsu, Tsan Sheng.

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

PY - 2009/12/1

Y1 - 2009/12/1

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

ER -