A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
From MaRDI portal
Publication:3549328
DOI10.1137/060649562zbMath1155.68090MaRDI 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
algorithms; combinatorial optimization; traveling salesman; approximation algorithm; planar graphs; graphs
Related Items
A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs, A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs, A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs, Unnamed Item, Unnamed Item, Travelling on graphs with small highway dimension, Catalan structures and dynamic programming in \(H\)-minor-free graphs, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs, Near-linear-time deterministic plane Steiner spanners for well-spaced point sets, 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, Unnamed Item, A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
