Scholarlink

<p>The Graphical Traveling Salesman Problem (GTSP) is defined on general graphs, unlike the classical TSP, which requires that the graph have at least one Hamiltonian cycle, and is generally defined, without loss of generality, over a complete graph. The Graphical Traveling Salesman Problem with Release Dates (GTSP-rd) extends the Graphical Traveling Salesman Problem (GTSP) by incorporating a release date for each vertex, which is the first time vertices become available to be visited. This paper focuses on GTSP-rd on paths, specifically minimizing the total traveled distance (GTSP-rd (distance)). We present a dynamic programming algorithm to solve GTSP-rd on paths with depot located in an extremity that achieves an <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_29_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="97" /> </InlineMediaObject> <EquationSource Format="TEX">\(O(n \log \log n)\)</EquationSource> </InlineEquation> time complexity, improving previous algorithms. Additionally, we discuss extensions of our approach to paths with the depot located at an arbitrary vertex with <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_29_Article_IEq2.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="103" /> </InlineMediaObject> <EquationSource Format="TEX">\(O(n^2 \log \log n)\)</EquationSource> </InlineEquation> time complexity.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Complexity on Paths for the Graphical TSP with Release Dates

  • 期刊论文

  • 发表日期：

    2025年9月24日

查看全文
  • Thailsson Clementino,
  • Rosiane de Freitas

摘要

The Graphical Traveling Salesman Problem (GTSP) is defined on general graphs, unlike the classical TSP, which requires that the graph have at least one Hamiltonian cycle, and is generally defined, without loss of generality, over a complete graph. The Graphical Traveling Salesman Problem with Release Dates (GTSP-rd) extends the Graphical Traveling Salesman Problem (GTSP) by incorporating a release date for each vertex, which is the first time vertices become available to be visited. This paper focuses on GTSP-rd on paths, specifically minimizing the total traveled distance (GTSP-rd (distance)). We present a dynamic programming algorithm to solve GTSP-rd on paths with depot located in an extremity that achieves an \(O(n \log \log n)\) time complexity, improving previous algorithms. Additionally, we discuss extensions of our approach to paths with the depot located at an arbitrary vertex with \(O(n^2 \log \log n)\) time complexity.