Complexity on paths for the graphical TSP with release dates

DOI10.1007/S44425-025-00029-0MaRDI QIDQ7402534zbMATH OpenFDO

Authors Thailsson Clementino, Rosiane de Freitas

Publication date 2026

Published in Matemática Contemporânea (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S44425-025-00029-0

zbMATH Keywords

algorithmsgraph theorypathspolynomial complexitytravelling salesman problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A new integer programming formulation of the graphical traveling salesman problem
• A survey on priority queues
• An iterated local search for the traveling salesman problem with release dates and completion time minimization
• Complexity of routing problems with release dates
• Complexity of routing problems with release dates and deadlines
• Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph
• On RAM Priority Queues
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• The traveling salesman problem on a graph and some related integer polyhedra

This page was built for publication: Complexity on paths for the graphical TSP with release dates

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