Approximation Algorithms for Several Graph Augmentation Problems
Greg N. Frederickson, Joseph F. JáJá · SIAM Journal on Computing · 1981
Graph augmentation problems on a weighted graph involve determining a minimum-cost set of edges to add to a graph to satisfy a specified property, such as biconnectivity, bridge-connectivity or strong connectivity. These augmentation problems are shown to be NP-complete in the restricted case of the graph being initially connected. Approximation algorithms with favorable time complexity are presented and shown to have constant worst-case performance ratios.
Cited by 259 works. doi:10.1137/0210019
Authors
References
- Reducibility among Combinatorial Problems
- Shortest Connection Networks And Some Generalizations
- Approximation algorithms for combinatorial problems
- On the Computational Complexity of Combinatorial Problems
- Finding Minimum Spanning Trees
- Optimum branchings
- An 0(|E|loglog|V|) algorithm for finding minimum spanning trees
- Finding optimum branchings
- Augmentation Problems
- Priority queues with update and finding minimum spanning trees