Efficiently solvable special cases of bottleneck travelling salesman problems

DOI10.1016/0166-218X(91)90024-QzbMath0747.90081OpenAlexW1970388956MaRDI QIDQ1179263

W. Sandholzer, Rainer E. Burkard

Publication date: 26 June 1992

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

Full work available at URL: https://doi.org/10.1016/0166-218x(91)90024-q

zbMATH Keywords

pyramidal toursufficient optimality conditionsbottleneck travelling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items

Coloring Toeplitz graphs ⋮ An Oracle Strongly Polynomial Algorithm for Bottleneck Expansion Problems ⋮ Special cases of travelling salesman problems and heuristics ⋮ On the recognition of permuted bottleneck Monge matrices ⋮ On the role of bottleneck Monge matrices in combinatorial optimization ⋮ The two-stripe symmetric circulant TSP is in P ⋮ Hamiltonian cycles in circulant digraphs with two stripes ⋮ The property of Hamiltonian connectedness in Toeplitz graphs ⋮ Extending single tolerances to set tolerances ⋮ Pyramidal tours and multiple objectives ⋮ Hamiltonian properties of Toeplitz graphs ⋮ Perspectives of Monge properties in optimization ⋮ On \(t\)-diagnosability of multicore systems with symmetric circulant structure ⋮ On the reflexive edge strength of the circulant graphs ⋮ The Pfaffian property of Cayley graphs on dihedral groups ⋮ Monge properties, discrete convexity and applications ⋮ A comparison of lower bounds for the symmetric circulant traveling salesman problem ⋮ Coloring planar Toeplitz graphs and the stable set polytope. ⋮ Well-solved cases of the 2-peripatetic salesman problem ⋮ The Pfaffian property of circulant graphs ⋮ On the chromatic number of Toeplitz graphs ⋮ Minimizing the number of workers in a paced mixed-model assembly line ⋮ On Hamiltonian paths in distance graphs ⋮ The algebraic Monge property and path problems ⋮ A class of bottleneck expansion problems ⋮ Characterizing bipartite Toeplitz graphs ⋮ Long cycles and paths in distance 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 ⋮ Unnamed Item ⋮ An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices

Cites Work

• Extreme Hamiltonian lines
• Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems
• A solvable case of the traveling salesman problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item