Graphical Traveling Salesman Problem With Release Dates in Path-like Graphs: Algorithms and Complexity
Loading...
Date
Authors
Advisor(s)
Co-advisor(s)
Committee members
Moura, Edleno Silva de Moura
Delle-Done, Diego
Ravelo, Santiago Valdés
Delle-Done, Diego
Ravelo, Santiago Valdés
Graduate program
Journal Title
Journal ISSN
Volume Title
Publisher
Universidade Federal do Amazonas
Type
Access rights
DOI
Resumo (Portuguese)
In this dissertation, we investigates the Graphical Traveling Salesman Problem with Release Dates (GTSP-rd), a generalization of the classical NP-hard TSP in which each vertex has an associated release date, the earliest time a vertex becomes available to be served. Unlike the traditional approach of transforming the input into a complete graph, the GTSP-rd is solved directly on the original graph, preserving structural properties that may admit more efficient algorithms for special cases. Motivated by real-world applications such as logistics in grid-based warehouses, rural road networks, and sameday express deliveries in general, this work aims to determine for which graph classes the GTSP-rd can be solved in polynomial time. Based on previous polynomial-time results for path graphs and a few other structures, this research focuses on Path-like graphs, including paths, cycles, stars, caterpillars, lobsters, and subdivided stars. Thus, this work provides: (i) a precise and explicit formulation of the GTSP-rd, filling gaps in the existing literature; (ii) improved linear and near-linear algorithms for paths with the depot at an extremity; (iii) new polynomial-time dynamic programming algorithms for general paths, stars, and cycles; and (iv) structural insights and partial results for caterpillar, lobster and subdivided stars. Overall, this work advances the understanding of how graph structure influences the computational complexity of the GTSP-rd, expands the set of graph classes known to admit polynomial-time solutions, and establishes new theoretical insights that may support further progress toward a broader characterization of other tractable cases.
Abstract
In this dissertation, we investigates the Graphical Traveling Salesman Problem with Release Dates (GTSP-rd), a generalization of the classical NP-hard TSP in which each vertex has an associated release date, the earliest time a vertex becomes available to be served. Unlike the traditional approach of transforming the input into a complete graph, the GTSP-rd is solved directly on the original graph, preserving structural properties that may admit more efficient algorithms for special cases. Motivated by real-world applications such as logistics in grid-based warehouses, rural road networks, and sameday express deliveries in general, this work aims to determine for which graph classes the GTSP-rd can be solved in polynomial time. Based on previous polynomial-time results for path graphs and a few other structures, this research focuses on Path-like graphs, including paths, cycles, stars, caterpillars, lobsters, and subdivided stars. Thus, this work provides: (i) a precise and explicit formulation of the GTSP-rd, filling gaps in the existing literature; (ii) improved linear and near-linear algorithms for paths with the depot at an extremity; (iii) new polynomial-time dynamic programming algorithms for general paths, stars, and cycles; and (iv) structural insights and partial results for caterpillar, lobster and subdivided stars. Overall, this work advances the understanding of how graph structure influences the computational complexity of the GTSP-rd, expands the set of graph classes known to admit polynomial-time solutions, and establishes new theoretical insights that may support further progress toward a broader characterization of other tractable cases.
Description
Controlled term
Sustainable Development Goals (SDG)
Citation
ANDRADE, Thailsson Clementino de. Graphical Traveling Salesman Problem With Release Dates in Path-like
Graphs: Algorithms and Complexity. 2026. 74 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus (AM), 2026.
Collections
Endorsement
Review
Supplemented By
Referenced By
Creative Commons license
Except where otherwise noted, this item's license is described as Acesso Aberto

