Efficiently solvable special cases of bottleneck travelling salesman problems
DOI10.1016/0166-218X(91)90024-QzbMATH Open0747.90081OpenAlexW1970388956MaRDI QIDQ1179263FDOQ1179263
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
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
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Extreme Hamiltonian lines
- Title not available (Why is that?)
- Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A solvable case of the traveling salesman problem
Cited In (36)
- Title not available (Why is that?)
- Coloring planar Toeplitz graphs and the stable set polytope.
- 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
- Title not available (Why is that?)
- On \(t\)-diagnosability of multicore systems with symmetric circulant structure
- Long cycles and paths in distance graphs
- Characterizing bipartite Toeplitz graphs
- A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
- Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
- Hamiltonian properties of Toeplitz graphs
- An Oracle Strongly Polynomial Algorithm for Bottleneck Expansion Problems
- Extending single tolerances to set tolerances
- The two-stripe symmetric circulant TSP is in P
- The Pfaffian property of circulant graphs
- 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)
