A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs
From MaRDI portal
Publication:5002603
DOI10.4230/LIPIcs.APPROX-RANDOM.2017.3zbMath1467.68137arXiv1611.03889OpenAlexW2749358524MaRDI QIDQ5002603
Baigong Zheng, Glencora Borradaile
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1611.03889
Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25) Connectivity (05C40)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- A factor 2 approximation algorithm for the generalized Steiner network problem
- The knapsack problem with neighbour constraints
- A subset spanner for Planar graphs, with application to subset TSP
- Removable edges in 3-connected graphs
- The Two-Edge Connectivity Survivable Network Problem in Planar Graphs
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- Approximation Algorithms for Several Graph Augmentation Problems
- Augmentation Problems
- Biconnectivity approximations and graph carvings
- Approximation algorithms for NP-complete problems on planar graphs
- The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs
- Algorithms – ESA 2005
This page was built for publication: A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs
