Approximate TSP in graphs with forbidden minors. (English) Zbl 0973.68263
Montanari, Ugo (ed.) et al., Automata, languages and programming. 27th international colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1853, 869-877 (2000).
Summary: Given as input an edge-weighted graph, we analyze two algorithms for finding subgraphs with low total edge weight. The first algorithm finds a separator subgraph with a small number of components, and is analyzed for graphs with an arbitrary excluded minor. The second algorithm finds a spanner with small stretch factor, and is analyzed for graphs in a hereditary family \({\mathcal G}(k)\). These results imply (i) a QPTAS (Quasi-Polynomial Time Approximation Scheme) for the TSP (Traveling Salesperson Problem) in unweighted graphs with an excluded minor, and (ii) a QPTAS for the TSP in weighted graphs with bounded genus.
For the entire collection see [Zbl 0941.00034].
For the entire collection see [Zbl 0941.00034].
MSC:
68W25 | Approximation algorithms |
05C85 | Graph algorithms (graph-theoretic aspects) |
68Q25 | Analysis of algorithms and problem complexity |
90C35 | Programming involving graphs or networks |