Recent Development of Graph Connectivity Augmentation Algorithms

Hiroshi NAGAMOCHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.3   pp.372-383
Publication Date: 2000/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Graph Algorithms
Keyword: 
edge-connectivity,  vertex-connectivity,  minimum cuts,  graphs,  augmentation problem,  polynomial algorithm,  

Full Text: PDF(396.2KB)>>
Buy this Article




Summary: 
The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem has been extensively studied, and several efficient algorithm have been discovered. We survey the recent development of the algorithms for this problem. In particular, we show how the minimum cut algorithm due to Nagamochi and Ibaraki is effectively applied to solve the edge-connectivity augmentation problem.