Cover Image

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Choudhary, Keerti, Kumar, Amit, Saggi, Lakshay
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

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
by: Ahi, Mridul, et al.
Published: (2025)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
by: Pilipczuk, Michał, et al.
Published: (2025)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
by: Chitnis, Rajesh, et al.
Published: (2024)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

Simpler and Improved Replacement Path Coverings
by: Bilò, Davide, et al.
Published: (2026)

The Steiner Shortest Path Tree Problem
by: Asher, Omer, et al.
Published: (2025)

On the Two Paths Theorem and the Two Disjoint Paths Problem
by: Humeau, Samuel, et al.
Published: (2025)

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
by: Bilò, Davide, et al.
Published: (2024)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
by: Chen, Kuowen, et al.
Published: (2025)

Fault-Tolerant Bounded Flow Preservers
by: Bansal, Shivam, et al.
Published: (2024)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

Revisiting Directed Disjoint Paths on tournaments (and relatives)
by: Gomes, Guilherme C. M., et al.
Published: (2025)

Shortest Paths in Multimode Graphs
by: Kirkpatrick, Yael, et al.
Published: (2025)

On Constrained and k Shortest Paths
by: Bendahi, Abderrahim, et al.
Published: (2024)

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Greedy Conjecture for the Shortest Common Superstring Problem and its Strengthenings
by: Nikolaev, Maksim
Published: (2024)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2024)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
by: Bhaskar, Umang, et al.
Published: (2025)

Hierarchical Multicriteria Shortest Path Search
by: Kurbanov, Temirlan, et al.
Published: (2025)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Shortcutting for Negative-Weight Shortest Path
by: Li, George Z., et al.
Published: (2025)

Verifying Shortest Paths in Linear Time
by: Shokry, Ahmed, et al.
Published: (2024)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

Enhanced Methods for the Weight Constrained Shortest Path Problem
by: Ahmadi, Saman, et al.
Published: (2022)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
by: Górkiewicz, Adam, et al.
Published: (2025)

Fully Dynamic Shortest Paths in Sparse Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Parameterized Complexity of Finding Dissimilar Shortest Paths
by: Funayama, Ryo, et al.
Published: (2024)

Breaking the Bellman-Ford Shortest-Path Bound
by: Elmasry, Amr
Published: (2024)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2025)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
by: Włodarczyk, Michał
Published: (2024)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
by: Ferdous, S M, et al.
Published: (2023)

Fault-Tolerant ST-Diameter Oracles
by: Bilò, Davide, et al.
Published: (2023)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
by: Bilò, Davide, et al.
Published: (2024)

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

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
by: Fischer, Nick, et al.
Published: (2024)