On the Maximum Scatter Traveling Salesperson Problem

DOI10.1137/S0097539797320281zbMath0942.90035MaRDI QIDQ4268895

Esther M. Arkin, Yi-Jen Chiang, Joseph S. B. Mitchell, Steven S. Skiena, Tae-Cheon Yang

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

optimizationmatchingtraveling salesman problemapproximation algorithmsDirac's theorembottleneck TSPmaximum scatter TSPtraveling salesperson problemHamiltonian cycle/pathPosa conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items (7)

The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis ⋮ The traveling salesman problem on grids with forbidden neighborhoods ⋮ The balanced traveling salesman problem ⋮ A branch-and-cut algorithm for the balanced traveling salesman problem ⋮ Minimizing the number of workers in a paced mixed-model assembly line ⋮ A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions ⋮ Experimental analysis of heuristics for the bottleneck traveling salesman problem

This page was built for publication: On the Maximum Scatter Traveling Salesperson Problem