Cover Image

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Kuowen, Wein, Nicole, Zhang, Yiran
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

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

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

New Results on a General Class of Minimum Norm Optimization Problems
by: Chen, Kuowen, et al.
Published: (2025)

Settling Weighted Token Swapping up to Algorithmic Barriers
by: Wein, Nicole, et al.
Published: (2025)

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

Edge-Minimum Walk of Modular Length in Polynomial Time
by: Amarilli, Antoine, et al.
Published: (2024)

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

Single-Source Shortest Path Problem in Weighted Disk Graphs
by: An, Shinwoo, et al.
Published: (2025)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
by: Brewer, Bruce W., et al.
Published: (2024)

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

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
by: Li, Jason, 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)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
by: Choudhary, Keerti, et al.
Published: (2025)

Closing the Gap Between Directed Hopsets and Shortcut Sets
by: Bernstein, Aaron, et al.
Published: (2022)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
by: Haeupler, Bernhard, et al.
Published: (2025)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
by: Bernstein, Aaron, et al.
Published: (2022)

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

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

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

On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2023)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
by: Li, Jason
Published: (2025)

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

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

Finding a Shortest $M$-link Path in a Monge Directed Acyclic Graph
by: Wan, Joy Z.
Published: (2024)

All-Pairs Shortest Paths with Few Weights per Node
by: Abboud, Amir, et al.
Published: (2025)

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
by: Geis, Lukas, et al.
Published: (2024)

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

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

A Faster Directed Single-Source Shortest Path Algorithm
by: Duan, Ran, et al.
Published: (2026)

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2025)

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
by: Bentert, Matthias, et al.
Published: (2026)

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)

Improved Online Sorting
by: Nirjhor, Jubayer, et al.
Published: (2025)

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

A Polynomial-time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs
by: Cenciarelli, Pietro, et al.
Published: (2016)

Beyond 2-approximation for k-Center in Graphs
by: Jin, Ce, et al.
Published: (2025)

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

Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics
by: Cauvi, Justine, et al.
Published: (2025)

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