A subexponential parameterized algorithm for subset TSP on planar graphs

DOI10.1137/1.9781611973402.131MaRDI QIDQ5384093zbMATH OpenOpenAlexFDO

Authors Dániel Marx, Philip N. Klein

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973402.131

Mathematics Subject Classification ID

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

Recommendations

• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• A subset spanner for Planar graphs, with application to subset TSP
• scientific article; zbMATH DE number 1303538
• The parameterized complexity of local search for TSP, more refined
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights

Cited in

(25)

• An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• On polynomial kernels for traveling salesperson problem and its generalizations
• TSP in a simple polygon
• A PTAS for k-hop MST on the Euclidean plane: improving dependency on k
• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• Parameterized approximation algorithms for bidirected Steiner network problems
• A subset spanner for Planar graphs, with application to subset TSP
• Waypoint routing on bounded treewidth graphs
• Subexponential parameterized algorithms for graphs of polynomial growth
• Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
• On the exact \& approximate complexity of the strongly connected Steiner subgraph problem on two terminals with demands
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Subexponential parameterized directed Steiner network problems on planar graphs: a complete classification
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
• Linear kernels for outbranching problems in sparse digraphs
• An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• An exponential time parameterized algorithm for planar disjoint paths
• The parameterized complexity of local search for TSP, more refined
• Walking through waypoints
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
• Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP

This page was built for publication: A subexponential parameterized algorithm for subset TSP on planar graphs

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