TSP tour domination and Hamilton cycle decompositions of regular digraphs

DOI10.1016/S0167-6377(01)00053-0zbMath1103.90390OpenAlexW2027528755MaRDI QIDQ5939600

Anders Yeo, Gregory Gutin

Publication date: 2001

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(01)00053-0

zbMATH Keywords

ATSPDomination analysisHamilton cycle decompositionRegular digraphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items

Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Upper bounds on ATSP neighborhood size. ⋮ Hamilton decompositions of regular expanders: applications ⋮ Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ Dominance guarantees for above-average solutions ⋮ Minimum number of below average triangles in a weighted complete graph ⋮ A survey of very large-scale neighborhood search techniques ⋮ A domination algorithm for {0,1}-instances of the travelling salesman problem ⋮ Anti-matroids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Hamiltonian decomposition of \(K^*_{2m},2m\geq 8\)
• Exponential neighbourhood local search for the traveling salesman problem
• Small diameter neighbourhood graphs for the traveling salesman problem: At most four moves from tour to tour
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Domination analysis of some heuristics for the traveling salesman problem
• The Travelling Salesman and the PQ-Tree
• The traveling salesman problem: new polynomial approximation algorithms and domination analysis
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Implementation of a linear time algorithm for certain generalized traveling salesman problems
• A new heuristic for the traveling salesman problem
• Construction heuristics for the asymmetric TSP.