A subset spanner for Planar graphs, with application to subset TSP
From MaRDI portal
Publication:2931435
DOI10.1145/1132516.1132620zbMath1301.05335OpenAlexW2065166038MaRDI QIDQ2931435
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132620
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (11)
Multi-priority graph sparsification ⋮ Approximation algorithms via contraction decomposition ⋮ The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs ⋮ Near-linear-time deterministic plane Steiner spanners for well-spaced point sets ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs ⋮ Light Euclidean Spanners with Steiner Points ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems ⋮ Unnamed Item
This page was built for publication: A subset spanner for Planar graphs, with application to subset TSP
