Bounds for the symmetric 2-peripatetic salesman problem

DOI10.1080/02331939208843770zbMath0814.05066OpenAlexW2086830346MaRDI QIDQ4327897

Jeroen B. J. M. De Kort

Publication date: 13 June 1995

Published in: Optimization (Search for Journal in Brave)

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

zbMATH Keywords

heuristicsgreedy algorithmedge-disjoint Hamiltonian cycles2-peripatetic salesman problemNP- hardness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Sensitivity analysis for symmetric 2-peripatetic salesman problems ⋮ Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph ⋮ Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services ⋮ 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 ⋮ A branch and bound algorithm for symmetric 2-peripatetic salesman problems ⋮ A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem

Cites Work

• Unnamed Item
• Disjoint paths in a rectilinear grid
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Disjoint paths in a network
• The traveling-salesman problem and minimum spanning trees: Part II
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Lower bounds for symmetricK-peripatetic salesman problems

This page was built for publication: Bounds for the symmetric 2-peripatetic salesman problem