Well-solved cases of the 2-peripatetic salesman problem
From MaRDI portal
Publication:4351794
DOI10.1080/02331939708844286zbMath0886.90120OpenAlexW2080771472MaRDI QIDQ4351794
M. J. D. de Brey, A. Volgenant
Publication date: 23 October 1997
Published in: Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/02331939708844286
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph, A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP, Safe and secure vehicle routing: a survey on minimization of risk exposure, An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution, Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph, A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem, A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP, 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
