Cover Image

Improving polynomial bounds for the Graphical Traveling Salesman Problem with release dates on paths

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Clementino, Thailsson, de Freitas, Rosiane
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths
by: Castro, Lucas, et al.
Published: (2025)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
by: Antoniadis, Antonios, et al.
Published: (2020)

A faster heuristic for the Traveling Salesman Problem with Drone
by: Hokama, Pedro H. D. B., et al.
Published: (2024)

Approximating Traveling Salesman Problems Using a Bridge Lemma
by: Böhm, Martin, et al.
Published: (2024)

Parameterized Complexity of Directed Traveling Salesman Problem
by: Blažej, Václav, et al.
Published: (2025)

C*: A New Bounding Approach for the Moving-Target Traveling Salesman Problem
by: Philip, Allen George, et al.
Published: (2023)

A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
by: Saller, Sophia, et al.
Published: (2023)

Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
by: Soulignac, Francisco J.
Published: (2025)

Exploring Monotone Priority Queues for Dijkstra Optimization
by: Costa, Jonas, et al.
Published: (2024)

Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems
by: Wang, Long, et al.
Published: (2025)

A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length
by: Ghaseminia, Benyamin, et al.
Published: (2025)

Retroactive Monotonic Priority Queues via Range Searching
by: Castro, Lucas, et al.
Published: (2025)

The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Effective Traveling for Metric Instances of the Traveling Thief Problem
by: Eube, Jan, et al.
Published: (2026)

The APX-hardness of the Traveling Tournament Problem
by: Zhao, Jingyang, et al.
Published: (2023)

The Canadian Traveller Problem on outerplanar graphs
by: Beaudou, Laurent, et al.
Published: (2024)

A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets
by: Philip, Allen George, et al.
Published: (2024)

Stochastic Traveling Salesperson Problem with Neighborhoods for Object Detection
by: Peng, Cheng, et al.
Published: (2024)

Time complexity of the Analyst's Traveling Salesman algorithm
by: Ramirez, Anthony, et al.
Published: (2022)

An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling
by: Zhao, Jingyang, et al.
Published: (2025)

Routing on Sparse Graphs with Non-metric Costs for the Prize-collecting Travelling Salesperson Problem
by: O'Hara, Patrick, et al.
Published: (2024)

Improved bounds for group testing in arbitrary hypergraphs
by: De Bonis, Annalisa
Published: (2024)

4/3-Approximation of Graphic TSP
by: Çivril, Ali
Published: (2023)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
by: Bencs, Ferenc, et al.
Published: (2025)

Improved Approximations for Dial-a-Ride Problems
by: Zhao, Jingyang, et al.
Published: (2026)

Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
by: Jenssen, Matthew, et al.
Published: (2023)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

Beating Competitive Ratio 4 for Graphic Matroid Secretary
by: Banihashem, Kiarash, et al.
Published: (2025)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters $k$-clustering and their fair variants
by: Banerjee, Sandip, et al.
Published: (2025)

Improved Approximation Ratios for the Shortest Common Superstring Problem with Reverse Complements
by: Yamano, Ryosuke, et al.
Published: (2026)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
by: Frei, Fabian, et al.
Published: (2025)

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks
by: Blauth, Jannis, et al.
Published: (2022)

Minimizing Total Travel Time for Collaborative Package Delivery with Heterogeneous Drones
by: Erlebach, Thomas, et al.
Published: (2026)

Approximating the shortest path problem with scenarios
by: Kasperski, Adam, et al.
Published: (2018)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

On polynomial kernelization for Stable Cutset
by: Kratsch, Stefan, et al.
Published: (2024)

Canadian Traveller Problems in Temporal Graphs
by: Bellitto, Thomas, et al.
Published: (2024)