Approximation algorithms for not necessarily disjoint clustered TSP

DOI10.7155/JGAA.00478MaRDI QIDQ4554892zbMATH OpenOpenAlexWikidataFDO

Authors Nili Guttmann-Beck, Eyal Knaan, Michal Stern

Publication date 12 November 2018

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

clustered traveling salesman problemshortest Hamiltonian path

Mathematics Subject Classification ID

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

Recommendations

• An approximation algorithm for the clustered path travelling salesman problem
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• scientific article; zbMATH DE number 1302021
• An improved approximation algorithm for the clustered traveling salesman problem
• An approximation algorithm for the clustered path travelling salesman problem

Cites work

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

Cited in

(12)

• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• A note on approximation algorithms of the clustered traveling salesman problem
• Vertices removal for feasibility of clustered spanning trees
• scientific article; zbMATH DE number 1302021 (Why is no real title available?)
• Local search for Hamiltonian Path with applications to clustering visitation paths
• Improving approximation ratios for the clustered traveling Salesman problem
• Recent Advances in Constraints
• An approximation algorithm for the clustered path travelling salesman problem
• Achieving feasibility for clustered traveling salesman problems using PQ‐trees
• An approximation algorithm for the clustered path travelling salesman problem
• A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
• Better approximation algorithms for clustered TSP and subgroup planning

This page was built for publication: Approximation algorithms for not necessarily disjoint clustered TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554892)