A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
From MaRDI portal
Recommendations
Cited in
(37)- A linear time approximation scheme for computing geometric maximum \(k\)-star
- The power of the weighted sum scalarization for approximating multiobjective optimization problems
- The simultaneous semi-random model for TSP
- Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs
- Better approximability results for min-max tree/cycle/path cover problems
- Routing vehicles to minimize fuel consumption
- scientific article; zbMATH DE number 1670877 (Why is no real title available?)
- scientific article; zbMATH DE number 6347354 (Why is no real title available?)
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- scientific article; zbMATH DE number 1303538 (Why is no real title available?)
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Engineering an approximation scheme for traveling salesman in planar graphs
- 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
- Approximating asymmetric TSP in exponential time
- Approximating the regular graphic TSP in near linear time
- A (1+\varepsilon)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- A subexponential parameterized algorithm for subset TSP on planar graphs
- Exact distance oracles for planar graphs
- A polynomial-time approximation scheme for planar multiway cut
- Travelling on graphs with small highway dimension
- Exponential time approximation scheme for TSP
- The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
- The simultaneous semi-random model for TSP
- An improved upper bound for the universal TSP on the grid
- A gap-ETH-tight approximation scheme for Euclidean TSP
- Separator theorem and algorithms for planar hyperbolic graphs
- Light, reliable spanners
- True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
- TSP in a simple polygon
- A PTAS for k-hop MST on the Euclidean plane: improving dependency on k
- Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
- Robust contraction decomposition for minor-free graphs and its applications
- Approximation schemes for orienteering and deadline TSP in doubling metrics
- Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs
- Near-linear-time deterministic plane Steiner spanners for well-spaced point sets
This page was built for publication: A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549328)
