Approximation schemes for planar graph connectivity problems
From MaRDI portal
Cites work
- k-edge-connectivity: approximation and LP relaxation
- A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
- A (1.5+)-approximation algorithm for weighted connectivity augmentation
- A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
- A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
- A better-than-5/4-approximation for two-edge connectivity
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A General Approximation Technique for Constrained Forest Problems
- A PTAS for three-edge-connected survivable network design in planar graphs
- A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- An O(n n) approximation scheme for Steiner tree in planar graphs
- An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
- Approximating (unweighted) tree augmentation via lift-and-project. II
- Approximating connectivity domination in weighted bounded-genus graphs
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
- Approximation algorithms for connectivity augmentation problems
- Approximation Algorithms for Graph Augmentation
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximation algorithms via contraction decomposition
- Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs
- Augmenting the connectivity of planar and geometric graphs
- Beating approximation factor two for weighted tree augmentation with bounded costs
- Better-than-2 approximations for weighted tree augmentation and applications to Steiner tree
- Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
- Biconnectivity approximations and graph carvings
- Bidimensionality: new connections between FPT algorithms and PTASs
- Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
- Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
- Computing All Small Cuts in an Undirected Network
- Correlation clustering and two-edge-connected augmentation for planar graphs
- Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- scientific article; zbMATH DE number 6381762 (Why is no real title available?)
- scientific article; zbMATH DE number 1256750 (Why is no real title available?)
- scientific article; zbMATH DE number 1303538 (Why is no real title available?)
- scientific article; zbMATH DE number 1305417 (Why is no real title available?)
- scientific article; zbMATH DE number 1306896 (Why is no real title available?)
- scientific article; zbMATH DE number 6850362 (Why is no real title available?)
- Improved approximation for tree augmentation: saving by rewiring
- Improved Approximation for Two-Edge-Connectivity
- Improving on the 1. 5-approximation of a smallest 2-edge connected spanning subgraph
- Iterated rounding algorithms for the smallest k-edge connected spanning subgraph
- LP-relaxations for tree augmentation
- Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs
- On the relationship between the biconnectivity augmentation and traveling salesman problems
- On the tree augmentation problem
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
- Subgraph induced planar connectivity augmentation (extended abstract)
- Survivable network design for group connectivity in low-treewidth graphs
- The design of approximation algorithms
- The two-edge connectivity survivable-network design problem in planar graphs
- Two-Connected Augmentation Problems in Planar Graphs
This page was built for publication: Approximation schemes for planar graph connectivity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7349443)
