Augmentation Problems
Kapali P. Eswaran, Robert Endre Tarjan · SIAM Journal on Computing · 1976
This paper considers problems in which the object is to add a minimum-weight set of edges to a graph so as to satisfy a given connectivity condition. Simple characterizations of the minimum number of edges necessary to make a directed graph strongly connected and to make an undirected graph bridge-connected or biconnected are given. Efficient algorithms for finding such minimum sets of edges are discussed. It is shown that the weighted versions of these problems are NP-complete.
Cited by 313 works. doi:10.1137/0205044
Authors
References
- Reducibility among Combinatorial Problems
- Depth-First Search and Linear Graph Algorithms
- Finding Minimum Spanning Trees
- Algorithm 447: efficient algorithms for graph manipulation
- Optimum branchings
- An 0(|E|loglog|V|) algorithm for finding minimum spanning trees
- Finding optimum branchings
- A note on finding the bridges of a graph
- Connectivity considerations in the design of survivable networks
- On the hamiltonian completion problem