For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Recent Development of Graph Connectivity Augmentation Algorithms
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Graph Algorithms
edge-connectivity, vertex-connectivity, minimum cuts, graphs, augmentation problem, polynomial algorithm,
Full Text: PDF(396.2KB)>>
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.