A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs

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

zbMATH Keywords

planar graphspolynomial-time approximation schemesthree-edge connectivity

Mathematics Subject Classification ID

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