A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
From MaRDI portal
Publication:3549328
DOI10.1137/060649562zbMath1155.68090OpenAlexW2132169470MaRDI QIDQ3549328
Publication date: 22 December 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/060649562
Related Items (18)
A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ The simultaneous semi-random model for TSP ⋮ Better approximability results for min-max tree/cycle/path cover problems ⋮ A linear time approximation scheme for computing geometric maximum \(k\)-star ⋮ Near-linear-time deterministic plane Steiner spanners for well-spaced point sets ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Routing vehicles to minimize fuel consumption ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs ⋮ Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs ⋮ Travelling on graphs with small highway dimension ⋮ Unnamed Item ⋮ Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs ⋮ The power of the weighted sum scalarization for approximating multiobjective optimization problems ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
