Well-solved cases of the 2-peripatetic salesman problem

DOI10.1080/02331939708844286zbMath0886.90120MaRDI QIDQ4351794

A. Volgenant, M. J. D. de Brey

Publication date: 23 October 1997

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331939708844286

zbMATH Keywords

2-peripatetic salesman problem; edge-disjoint Hamiltonian cycles of minimal total length

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem, Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2

Cites Work

• Unnamed Item
• Efficiently solvable special cases of bottleneck travelling salesman problems
• A branch and bound algorithm for symmetric 2-peripatetic salesman problems
• An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices
• The convex-hull-and-line traveling salesman problem: A solvable case
• Two edge-disjoint hamiltonian cycles in the butterfly graph
• Solvable cases of the \(k\)-person Chinese postman problem
• Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems