Approximate TSP in Graphs with Forbidden Minors

No abstract is available for this paper.

• Publication year

  2000

• Venue

  International Colloquium on Automata, Languages and Programming

• Publication date

  2000-07-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/3-540-45022-X_73
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Graph Theory

  2016cited by this paper
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems

  1999cited by this paper
• A polynomial-time approximation scheme for weighted planar graph TSP

  1998cited by this paper
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

  1998cited by this paper
• An approximation scheme for planar graph TSP

  1995cited by this paper
• The Traveling Salesman Problem with Distances One and Two

  1993cited by this paper
• On sparse spanners of weighted graphs

  1993cited by this paper
• A separator theorem for graphs with an excluded minor and its applications

  1990influential reference
• An extremal function for contractions of graphs

  1984cited by this paper
• A Separator Theorem for Planar Graphs

  1977cited by this paper

• Highway Dimension: a Metric View

  2024cites this paper
• Exploration of graphs with excluded minors

  2023cites this paper
• Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1*

  2023cites this paper
• Bypassing the surface embedding: approximation schemes for network design in minor-free graphs

  2022cites this paper
• A Unified Framework of Light Spanners II: Fine-Grained Optimality

  2021cites this paper
• A Unified and Fine-Grained Approach for Light Spanners

  2020cites this paper
• A Unified Framework for Light Spanners

  2020cites this paper
• On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

  2020cites this paper
• Light Spanners for High Dimensional Norms via Stochastic Decompositions

  2018cites this paper
• A PTAS for subset TSP in minor-free graphs

  2018cites this paper
• Minor-Free Graphs Have Light Spanners

  2017cites this paper
• Light spanners for bounded treewidth graphs imply light spanners for $H$-minor-free graphs

  2017cites this paper
• The Greedy Spanner is Existentially Optimal

  2016cites this paper
• Light Spanners

  2014cites this paper
• Light Spanner and Monotone Tree

  2012cites this paper
• Light Spanners in Bounded Pathwidth Graphs

  2012cites this paper
• Finding Light Spanners in Bounded Pathwidth Graphs

  2011cites this paper
• Approximation Algorithms via Contraction DecompositionA preliminary version of this paper appears in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, January 2007

  2010cites this paper
• Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs

  2009cites this paper
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights

  2008cites this paper
• Catalan structures and dynamic programming in H-minor-free graphs

  2008influential citation
• Approximating TSP on metrics with bounded global growth

  2008cites this paper
• Approximation algorithms for bounded dimensional metric spaces

  2007cites this paper
• Grigni : [ 21 ] Well-Connected Separators for Planar

  2007cites this paper
• Approximation algorithms via contraction decomposition

  2007cites this paper
• A subset spanner for Planar graphs, with application to subset TSP

  2006cites this paper
• Improved lower and upper bounds for universal TSP in planar metrics

  2006influential citation
• A linear-time approximation scheme for TSP in planar graphs with edge-weights

  2005cites this paper
• Bidimensionality: new connections between FPT algorithms and PTASs

  2005cites this paper
• A linear-time approximation scheme for planar weighted TSP

  2005cites this paper
• Grigni: [21] Well-Connected Separators for Planar Graphs

  2004cites this paper
• Light spanners and approximate TSP in weighted graphs with forbidden minors

  2002cites this paper