Achieving feasibility for clustered traveling salesman problems using PQ‐trees

DOI10.1002/net.22164zbMath1529.90087MaRDI QIDQ6139372

Unnamed Author, Michal Stern, Nili Guttmann-Beck

Publication date: 18 December 2023

Published in: Networks (Search for Journal in Brave)

zbMATH Keywords

graph theorytraveling salesman problemfeasibility

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• A structure theorem for the consecutive 1's property
• Restricted delivery problems on a network

This page was built for publication: Achieving feasibility for clustered traveling salesman problems using PQ‐trees