Efficiently solvable special cases of bottleneck travelling salesman problems

DOI10.1016/0166-218X(91)90024-QMaRDI QIDQ1179263zbMATH OpenOpenAlexFDO

Authors 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

sufficient optimality conditionspyramidal tourbottleneck travelling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4027206
• An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• scientific article; zbMATH DE number 34438
• An Algorithm for the Bottleneck Traveling Salesman Problem

Cites work

• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 4037195 (Why is no real title available?)
• scientific article; zbMATH DE number 3748788 (Why is no real title available?)
• scientific article; zbMATH DE number 3554025 (Why is no real title available?)
• scientific article; zbMATH DE number 3632217 (Why is no real title available?)
• scientific article; zbMATH DE number 3371832 (Why is no real title available?)
• A solvable case of the traveling salesman problem
• Extreme Hamiltonian lines
• Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems

Cited in

(36)

• Coloring planar Toeplitz graphs and the stable set polytope.
• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• Monge properties, discrete convexity and applications
• A comparison of lower bounds for the symmetric circulant traveling salesman problem
• An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices
• Well-solved cases of the 2-peripatetic salesman problem
• Pyramidal tours and multiple objectives
• Minimizing the number of workers in a paced mixed-model assembly line
• Coloring Toeplitz graphs
• The property of Hamiltonian connectedness in Toeplitz graphs
• The Pfaffian property of Cayley graphs on dihedral groups
• On t-diagnosability of multicore systems with symmetric circulant structure
• scientific article; zbMATH DE number 500420 (Why is no real title available?)
• Long cycles and paths in distance graphs
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Characterizing bipartite Toeplitz graphs
• Hamiltonian properties of Toeplitz graphs
• Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
• Extending single tolerances to set tolerances
• An Oracle Strongly Polynomial Algorithm for Bottleneck Expansion Problems
• The Pfaffian property of circulant graphs
• The two-stripe symmetric circulant TSP is in P
• On the reflexive edge strength of the circulant graphs
• Perspectives of Monge properties in optimization
• Special cases of travelling salesman problems and heuristics
• On the role of bottleneck Monge matrices in combinatorial optimization
• The Travelling Salesman Problem in symmetric circulant matrices with two stripes
• On the chromatic number of Toeplitz graphs
• On Hamiltonian paths in distance graphs
• An efficient heuristic algorithm for the bottleneck traveling salesman problem
• Enforced Hamiltonian cycles in circulant graphs
• A class of bottleneck expansion problems
• On Gilmore-Gomory's open question for the bottleneck TSP.
• Hamiltonian cycles in circulant digraphs with two stripes
• On the recognition of permuted bottleneck Monge matrices
• The algebraic Monge property and path problems

This page was built for publication: Efficiently solvable special cases of bottleneck travelling salesman problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179263)