Graph Augmentation Problems

Participants, Overview, Selected results.



A graph is $k$-vertex (-edge, respectively) connected if you cannot disconnect the graph by removing less than $k$ vertices (edges, respectively) from the graph. The graph augmentation problem is the problem of adding as few edges as possible to the graph such that the resulting graph satisfies a given connectivity requirement. This is a very fundamental graph theoretical problem which has applications in designing reliable networks, drawing graphs, protecting statistical databasea ... etc.

Selected results

Updated April 20, 2009.
Created by Tsan-sheng Hsu, last updated April 18, 2001.