A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs
DOI10.1137/19M1304088zbMath1486.05294arXiv1707.02190OpenAlexW4226434845MaRDI QIDQ5071089
Marcin Pilipczuk, Dániel Marx, Michał Pilipczuk
Publication date: 20 April 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.02190
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Call routing and the ratcatcher
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals
- A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
- Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
- New upper bounds on the decomposability of planar graphs
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Known Algorithms for Edge Clique Cover are Probably Optimal
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Subexponential Time Algorithms for Embedding H-Minor Free Graphs
- Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs
- Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
- Coloring Graphs with Constraints on Connectivity
- A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting
- Approximating k-center in planar graphs
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
- A subexponential parameterized algorithm for Subset TSP on planar graphs
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Parameterized Algorithms
- Slightly Superexponential Parameterized Problems
This page was built for publication: A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs
