Efficiently solvable special cases of bottleneck travelling salesman problems (Q1179263): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Rainer E. Burkard / rank | |||
Property / author | |||
Property / author: Rainer E. Burkard / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5643797 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4193256 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3776619 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3768703 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4127641 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A solvable case of the traveling salesman problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3932608 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extreme Hamiltonian lines / rank | |||
Normal rank |
Latest revision as of 13:43, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficiently solvable special cases of bottleneck travelling salesman problems |
scientific article |
Statements
Efficiently solvable special cases of bottleneck travelling salesman problems (English)
0 references
26 June 1992
0 references
A special case of the bottleneck travelling salesman problem is investigated. For distance matrices that are circulant matrices, it is shown that the problem can be solved in \(O(n \log n)\) time in contrast with the sum version of the problem for which this is still an open question. Sufficient conditions are then derived under which the optimal solution is a pyramidal tour. Some, but not all of these, are analogues of the same conditions for the sum version of the problem. Finally, the problem can be solved in \(O(n \log n)\) time for cost matrices \(c_{i,j}=a_ ib_ j\) where \(a_ 1\leq a_ 2\cdots\) and \(b_ 1\geq b_ 2\cdots\). The solution is not always a pyramidal tour, in distinction with the sum version where this is always the case.
0 references
sufficient optimality conditions
0 references
bottleneck travelling salesman problem
0 references
pyramidal tour
0 references