Approximation Algorithms for Several Graph Augmentation Problems

Cited In (71)

Fast distributed approximation for TAP and 2-edge-connectivity
Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
A primal-dual approximation algorithm for generalized Steiner network problems
Tight bounds for online weighted tree augmentation
Tight bounds for online weighted tree augmentation
Vertex covering by paths on trees with its applications in machine translation
Evolutionary local search for the edge-biconnectivity augmentation problem
A minimum 3-connectivity augmentation of a graph
Approximating Transitive Reductions for Directed Networks
On the tree augmentation problem
Computing the 2-blocks of directed graphs
A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation
Parameterized approximation algorithms for bidirected Steiner network problems
Approximation algorithms for vertex-connectivity augmentation on the cycle
Path hitting in acyclic graphs
Flexible graph connectivity
The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
Faster approximation algorithms for weighted triconnectivity augmentation problems
Inapproximability of the Tutte polynomial
A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
Kernelization and complexity results for connectivity augmentation problems
An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
Structured connectivity augmentation
Minimum weight connectivity augmentation for planar straight-line graphs
Network flow spanners
On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs
Combinatorial analysis (nonnegative matrices, algorithmic problems)
A smallest augmentation to 3-connect a graph
Approximating minimum representations of key Horn functions
Regular augmentation of planar graphs
An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
Title not available (Why is that?)
Minimum weight connectivity augmentation for planar straight-line graphs
On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
A simple LP-based approximation algorithm for the matching augmentation problem
Approximation algorithms for graph augmentation
Edge-connectivity augmentation problems
On the relationship between the biconnectivity augmentation and traveling salesman problems
Flexible Graph Connectivity
Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs
Shorter tours and longer detours: uniform covers and a bit beyond
Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees
Inferring (biological) signal transduction networks via transitive reductions of directed graphs
LP-relaxations for tree augmentation
Approximation algorithms for constructing some required structures in digraphs
On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
2-node-connectivity network design
Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
Hardness of \(k\)-vertex-connected subgraph augmentation problem
On the cycle augmentation problem: hardness and approximation algorithms
On small-depth tree augmentations
An efficient approximation algorithm for the survivable network design problem
A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation
How to Secure Matchings Against Edge Failures
How to Secure Matchings against Edge Failures
An ETH-tight algorithm for bidirected Steiner connectivity
Strongly connected spanning subgraph for almost symmetric networks
2-node-connectivity network design
Node connectivity augmentation via iterative randomized rounding
Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
Correlation clustering and two-edge-connected augmentation for planar graphs
Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
Approximation algorithms for node and element connectivity augmentation problems
The capacitated \(m\) two node survivable star problem
A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
A PTAS for three-edge-connected survivable network design in planar graphs
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
Fast distributed approximation for TAP and 2-edge-connectivity

This page was built for publication: Approximation Algorithms for Several Graph Augmentation Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3910552)