Approximation Algorithms for Several Graph Augmentation Problems
From MaRDI portal
Publication:3910552
DOI10.1137/0210019zbMath0461.05040OpenAlexW2051699458MaRDI QIDQ3910552
Greg N. Frederickson, Joseph F. Ja'Ja'
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210019
Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Connectivity (05C40) Algorithms in computer science (68W99)
Related Items (71)
Flexible Graph Connectivity ⋮ Tight bounds for online weighted tree augmentation ⋮ Edge-connectivity augmentation problems ⋮ Approximating Transitive Reductions for Directed Networks ⋮ A primal-dual approximation algorithm for generalized Steiner network problems ⋮ Structured Connectivity Augmentation ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph ⋮ On the tree augmentation problem ⋮ On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs ⋮ Hardness of \(k\)-vertex-connected subgraph augmentation problem ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ Correlation clustering and two-edge-connected augmentation for planar graphs ⋮ The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm ⋮ On a partition LP relaxation for min-cost 2-node connected spanning subgraphs ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs ⋮ LP-relaxations for tree augmentation ⋮ Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP ⋮ On the relationship between the biconnectivity augmentation and traveling salesman problems ⋮ Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs ⋮ Shorter tours and longer detours: uniform covers and a bit beyond ⋮ Inferring (biological) signal transduction networks via transitive reductions of directed graphs ⋮ A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs ⋮ Inapproximability of the Tutte polynomial ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ How to Secure Matchings against Edge Failures ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ Approximation algorithms for constructing some required structures in digraphs ⋮ A minimum 3-connectivity augmentation of a graph ⋮ 2-node-connectivity network design ⋮ A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs ⋮ Minimum weight connectivity augmentation for planar straight-line graphs ⋮ A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation ⋮ A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation ⋮ Kernelization and complexity results for connectivity augmentation problems ⋮ Network flow spanners ⋮ A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation ⋮ On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem ⋮ Approximation algorithms for graph augmentation ⋮ Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions ⋮ Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation ⋮ A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem ⋮ Unnamed Item ⋮ Approximation algorithms for node and element connectivity augmentation problems ⋮ Regular augmentation of planar graphs ⋮ Path hitting in acyclic graphs ⋮ Faster approximation algorithms for weighted triconnectivity augmentation problems ⋮ A smallest augmentation to 3-connect a graph ⋮ How to Secure Matchings Against Edge Failures ⋮ Tight Bounds for Online Weighted Tree Augmentation ⋮ An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees ⋮ The capacitated m two node survivable star problem ⋮ An efficient approximation algorithm for the survivable network design problem ⋮ Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs ⋮ Vertex covering by paths on trees with its applications in machine translation ⋮ Computing the 2-blocks of directed graphs ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Strongly Connected Spanning Subgraph for Almost Symmetric Networks ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ On small-depth tree augmentations ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem ⋮ Approximating Minimum Representations of Key Horn Functions ⋮ An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree ⋮ Evolutionary local search for the edge-biconnectivity augmentation problem ⋮ 2-node-connectivity network design ⋮ Flexible graph connectivity
This page was built for publication: Approximation Algorithms for Several Graph Augmentation Problems
