APPROXIMATING ASYMMETRIC TSP IN EXPONENTIAL TIME
From MaRDI portal
Publication:5168426
DOI10.1142/S0129054114500051zbMath1291.68177MaRDI QIDQ5168426
Publication date: 4 July 2014
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
TSPtraveling salesman problemasymmetric traveling salesman problemapproximation schemeexponential-time algorithm
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Exact algorithms for exact satisfiability and number of perfect matchings
- Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
- Expected Computation Time for Hamiltonian Path problem
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- P-Complete Approximation Problems
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- The traveling-salesman problem and minimum spanning trees: Part II
This page was built for publication: APPROXIMATING ASYMMETRIC TSP IN EXPONENTIAL TIME
