Approximation Algorithms for Not Necessarily Disjoint Clustered TSP

DOI10.7155/jgaa.00478zbMath1400.05238OpenAlexW2899200421WikidataQ128974684 ScholiaQ128974684MaRDI QIDQ4554892

Eyal Knaan, Nili Guttmann-Beck, Michal Stern

Publication date: 12 November 2018

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00478

zbMATH Keywords

clustered traveling salesman problemshortest Hamiltonian path

Mathematics Subject Classification ID

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

Related Items (1)

Vertices removal for feasibility of clustered spanning trees

Cites Work

• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Procedures for travelling salesman problems with additional constraints
• A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
• The clustering matroid and the optimal clustering tree
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Incidence matrices and interval graphs
• The complete optimal stars-clustering-tree problem
• Restricted delivery problems on a network
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation Algorithms for Not Necessarily Disjoint Clustered TSP