Approximation Algorithms for Several Graph Augmentation Problems

1981/05/01 by Greg N. Frederickson, Joseph Ja’Ja’, Joseph F. JáJá · 20 citations
Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Graph Theory Research

paper · doi:10.1137/0210019

Abstract

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.

Citations

• Approximation algorithms for combinatorial problems
• Augmentation Problems

Cited by

• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Flexible Graph Connectivity: Approximating Network Design Problems Between 1- and 2-connectivity
• Approximation Schemes for Planar Graph Connectivity Problems
• Plane Strong Connectivity Augmentation
• Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II
• Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP
• The two-edge connectivity survivable-network design problem in planar graphs
• A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
• A 1.75 LP approximation for the Tree Augmentation Problem
• The Price of Connectivity Augmentation on Planar Graphs
• On the Tree Augmentation Problem
• Improved bicriteria approximation for k-edge-connectivity
• Bicriteria approximation for k-edge-connectivity
• k-Edge-Connectivity: Approximation and LP Relaxation
• Almost Tight Additive Guarantees for k-Edge-Connectivity
• Improved Approximation for Weighted Tree Augmentation with Bounded Costs
• Fast Biconnectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance
• A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
• Inapproximability of the Tutte polynomial
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

Related

• Augmentation Problems
• Augmenting graphs to minimize the diameter
• Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle
• Engineering Weighted Connectivity Augmentation Algorithms
• A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation