Approximation Algorithms for Several Graph Augmentation Problems

Cited in

(71)

A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation
Fast distributed approximation for TAP and 2-edge-connectivity
How to Secure Matchings Against Edge Failures
How to Secure Matchings against Edge Failures
Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
Tight bounds for online weighted tree augmentation
A primal-dual approximation algorithm for generalized Steiner network problems
Vertex covering by paths on trees with its applications in machine translation
An ETH-tight algorithm for bidirected Steiner connectivity
Evolutionary local search for the edge-biconnectivity augmentation problem
Tight bounds for online weighted tree augmentation
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
Path hitting in acyclic graphs
Approximation algorithms for vertex-connectivity augmentation on the cycle
Parameterized approximation algorithms for bidirected Steiner network problems
Flexible graph connectivity
Strongly connected spanning subgraph for almost symmetric networks
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
2-node-connectivity network design
Node connectivity augmentation via iterative randomized rounding
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+ approximation for k-connected subgraphs
A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
Structured connectivity augmentation
Correlation clustering and two-edge-connected augmentation for planar graphs
Minimum weight connectivity augmentation for planar straight-line graphs
Network flow spanners
Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
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
Regular augmentation of planar graphs
An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
Approximating minimum representations of key Horn functions
scientific article; zbMATH DE number 7205039 (Why is no real title available?)
Minimum weight connectivity augmentation for planar straight-line graphs
On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
Approximation algorithms for node and element connectivity augmentation problems
A simple LP-based approximation algorithm for the matching augmentation problem
The capacitated \(m\) two node survivable star problem
Edge-connectivity augmentation problems
On the relationship between the biconnectivity augmentation and traveling salesman problems
Approximation algorithms for graph augmentation
Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs
Flexible Graph Connectivity
A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
A PTAS for three-edge-connected survivable network design in planar graphs
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
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 a partition LP relaxation for min-cost 2-node connected spanning subgraphs
On the cycle augmentation problem: hardness and approximation algorithms
An efficient approximation algorithm for the survivable network design problem
Fast distributed approximation for TAP and 2-edge-connectivity
Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
On small-depth tree augmentations

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)