An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices

DOI10.1016/0166-218X(93)90152-EzbMath0801.90120MaRDI QIDQ1314323

Jack A. A. van der Veen

Publication date: 1 December 1994

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

zbMATH Keywords

Hamiltonian tourbottleneck traveling salesmancomplete weighted digraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (6)

Extending single tolerances to set tolerances ⋮ Perspectives of Monge properties in optimization ⋮ Well-solved cases of the 2-peripatetic salesman problem ⋮ Minimizing the number of workers in a paced mixed-model assembly line ⋮ Experimental analysis of heuristics for the bottleneck traveling salesman problem ⋮ Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficiently solvable special cases of bottleneck travelling salesman problems
• Universal conditions for algebraic travelling salesman problems to be efficiently solvable
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristic
• Algorithms for two bottleneck optimization problems
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem

This page was built for publication: An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices