Hamiltonian cycles in circulant digraphs with two stripes

DOI10.1016/S0012-365X(96)00298-1zbMath0895.05041MaRDI QIDQ1377694

Eranda Çela, Rainer E. Burkard, Gerhard J. Woeginger, Qi-Fan Yang

Publication date: 17 February 1998

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian cyclesHamiltonian cycletraveling salesman problemcirculant digraphsHamiltonian digraphsstripescirculant distance matrixnonzero stripes

Mathematics Subject Classification ID

Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (12)

Hamiltonian problems in directed graphs with simple row patterns ⋮ Efficiently solvable special cases of hard combinatorial optimization problems ⋮ The two-stripe symmetric circulant TSP is in P ⋮ Arc-disjoint and edge-disjoint Hamilton cycles in circulants with two jumps ⋮ A comparison of lower bounds for the symmetric circulant traveling salesman problem ⋮ Coloring planar Toeplitz graphs and the stable set polytope. ⋮ Characterizing bipartite Toeplitz graphs ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem ⋮ The Travelling Salesman Problem in symmetric circulant matrices with two stripes ⋮ OR Utopia ⋮ Hamilton cycles in circulant digraphs with prescribed number of distinct jumps ⋮ Miscellaneous Digraph Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Efficiently solvable special cases of bottleneck travelling salesman problems
• Circulants and their connectivities
• Universal conditions for algebraic travelling salesman problems to be efficiently solvable
• Connectivity of circulant digraphs
• ON THE PROBLEM OF JACOBSTHAL
• Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems

This page was built for publication: Hamiltonian cycles in circulant digraphs with two stripes