An Approximation Algorithm for the Three Depots Hamiltonian Path Problem

DOI10.1007/978-1-4614-5134-1_25zbMath1375.90297OpenAlexW2160014007MaRDI QIDQ4596182

Rezika Kheffache, Mhand Hifi, Rachid Ouafi, Aristotelis Giannakos

Publication date: 30 November 2017

Published in: Optimization Theory, Decision Making, and Operations Research Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-1-4614-5134-1_25

zbMATH Keywords

approximation algorithmtraveling salesman problemHamiltonian path problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Eulerian and Hamiltonian graphs (05C45)

Related Items (3)

Approximation algorithms for the \(k\)-depots Hamiltonian path problem ⋮ Approximation algorithms for multi-vehicle stacker crane problems ⋮ Approximating the multiple-depot multiple-terminal Hamiltonian path problem

Cites Work

• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• Matroids and a forest cover problem
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• Maximum matching and a polyhedron with 0,1-vertices
• Unnamed Item
• Unnamed Item

This page was built for publication: An Approximation Algorithm for the Three Depots Hamiltonian Path Problem