A subset spanner for Planar graphs, with application to subset TSP

DOI10.1145/1132516.1132620MaRDI QIDQ2931435zbMATH OpenOpenAlexFDO

Authors Philip N. Klein

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

zbMATH Keywords

approximation schemeplanar graphspannertraveling salesman problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• A subexponential parameterized algorithm for subset TSP on planar graphs
• A Better Approximation Algorithm for Finding Planar Subgraphs
• scientific article; zbMATH DE number 871895
• A note on the practicality of maximal planar subgraph algorithms
• scientific article; zbMATH DE number 1262806
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• A linear time algorithm for finding maximal planar subgraphs
• An O(m\log n)-Time Algorithm for the Maximal Planar Subgraph Problem
• Two new approximation algorithms for the maximum planar subgraph problem
• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs

Cited in

(23)

• Approximation algorithms via contraction decomposition
• The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
• Light spanners for high dimensional norms via stochastic decompositions
• scientific article; zbMATH DE number 1670877 (Why is no real title available?)
• scientific article; zbMATH DE number 1303538 (Why is no real title available?)
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• A PTAS for three-edge-connected survivable network design in planar graphs
• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
• A subexponential parameterized algorithm for subset TSP on planar graphs
• A polynomial-time approximation scheme for planar multiway cut
• Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
• Light Euclidean Spanners with Steiner Points
• Multi-priority graph sparsification
• A gap-ETH-tight approximation scheme for Euclidean TSP
• A unified framework of light spanners. I: Fast (yet optimal) constructions
• Light, reliable spanners
• A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• Greedy spanners in Euclidean spaces admit sublinear separators
• Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
• Robust contraction decomposition for minor-free graphs and its applications
• Near-linear-time deterministic plane Steiner spanners for well-spaced point sets

This page was built for publication: A subset spanner for Planar graphs, with application to subset TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931435)