Approximation Algorithms for Several Graph Augmentation Problems
From MaRDI portal
Cited in
(82)- A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
- Path hitting in acyclic graphs
- 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
- Combinatorial analysis (nonnegative matrices, algorithmic problems)
- Edge-connectivity augmentation problems
- On the relationship between the biconnectivity augmentation and traveling salesman problems
- A minimum 3-connectivity augmentation of a graph
- Faster approximation algorithms for weighted triconnectivity augmentation problems
- An efficient approximation algorithm for the survivable network design problem
- Evolutionary local search for the edge-biconnectivity augmentation problem
- LP-relaxations for tree augmentation
- Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
- On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
- A smallest augmentation to 3-connect a graph
- An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- A primal-dual approximation algorithm for generalized Steiner network problems
- Fast distributed approximation for TAP and 2-edge-connectivity
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Approximation algorithms for vertex-connectivity augmentation on the cycle
- On small-depth tree augmentations
- Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
- 2-node-connectivity network design
- Flexible graph connectivity
- A simple LP-based approximation algorithm for the matching augmentation problem
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Shorter tours and longer detours: uniform covers and a bit beyond
- On the cycle augmentation problem: hardness and approximation algorithms
- A 4+ approximation for k-connected subgraphs
- Approximation algorithms for constructing some required structures in digraphs
- Minimum weight connectivity augmentation for planar straight-line graphs
- An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
- On the tree augmentation problem
- Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
- Minimum weight connectivity augmentation for planar straight-line graphs
- 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
- Strongly connected spanning subgraph for almost symmetric networks
- Approximating Transitive Reductions for Directed Networks
- Fast distributed approximation for TAP and 2-edge-connectivity
- Structured connectivity augmentation
- The capacitated m two node survivable star problem
- A PTAS for three-edge-connected survivable network design in planar graphs
- Parameterized approximation algorithms for bidirected Steiner network problems
- Flexible Graph Connectivity
- How to Secure Matchings Against Edge Failures
- Tight bounds for online weighted tree augmentation
- scientific article; zbMATH DE number 7205039 (Why is no real title available?)
- How to Secure Matchings against Edge Failures
- Approximation algorithms for graph augmentation
- Computing the 2-blocks of directed graphs
- Approximating minimum representations of key Horn functions
- Node connectivity augmentation via iterative randomized rounding
- Correlation clustering and two-edge-connected augmentation for planar graphs
- Hardness of \(k\)-vertex-connected subgraph augmentation problem
- On a partition LP relaxation for min-cost 2-node connected spanning subgraphs
- 2-node-connectivity network design
- An ETH-tight algorithm for bidirected Steiner connectivity
- Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
- A (1.5+)-approximation algorithm for weighted connectivity 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
- Approximation algorithms for node and element connectivity augmentation problems
- On the constrained Steiner strong connectivity augmentation problem
- Distributed graph augmentation protocols to achieve strong connectivity in multi-agent networks
- Better-than-2 approximations for weighted tree augmentation and applications to Steiner tree
- Approximation algorithms for Steiner connectivity augmentation
- Protecting the connectivity of a graph under non-uniform edge failures
- Protecting the connectivity of a graph under nonuniform edge failures
- Bicriteria approximation for k-edge-connectivity
- Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
- Approximation schemes for planar graph connectivity problems
- The price of connectivity augmentation on planar graphs
- Resilient monitoring of social dynamical systems through collaborative multi-agent networks under latency
- Regular augmentation of planar graphs
- Tight bounds for online weighted tree augmentation
- On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs
- Inferring (biological) signal transduction networks via transitive reductions of directed graphs
- Inapproximability of the Tutte polynomial
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)
