A subexponential parameterized algorithm for Subset TSP on planar graphs

DOI10.1137/1.9781611973402.131zbMath1423.68214OpenAlexW4241892047MaRDI QIDQ5384093

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

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)

Related Items (14)

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times ⋮ Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane ⋮ A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ Waypoint routing on bounded treewidth graphs ⋮ Walking through waypoints ⋮ The complexity of tree partitioning ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Subexponential parameterized algorithms for graphs of polynomial growth ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

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