Cover Image

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ashvinkumar, Vikrant, Bernstein, Aaron, Karczmarz, Adam
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

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

Low Sensitivity Hopsets
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
by: Ashvinkumar, Vikrant, et al.
Published: (2023)

Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
by: Ashvinkumar, Vikrant, et al.
Published: (2025)

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

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

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
by: Li, Jason, et al.
Published: (2025)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
by: Karczmarz, Adam, et al.
Published: (2025)

Faster Algorithms for Shortest Unique or Absent Substrings
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

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

Vantage Point Selection Algorithms for Bottleneck Capacity Estimation
by: Ashvinkumar, Vikrant, et al.
Published: (2025)

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

Fully Dynamic Strongly Connected Components in Planar Digraphs
by: Karczmarz, Adam, et al.
Published: (2024)

Fully Dynamic Algorithms for Transitive Reduction
by: Goranci, Gramoz, et al.
Published: (2025)

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

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

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

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
by: Karczmarz, Adam, et al.
Published: (2024)

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

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, 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)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

Improved 2-Approximate Shortest Paths for close vertex pairs
by: Gupta, Manoj
Published: (2025)

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

Massively Parallel Algorithms for Approximate Shortest Paths
by: Dory, Michal, et al.
Published: (2024)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

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

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

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

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

Faster Algorithms for Dual-Failure Replacement Paths
by: Chechik, Shiri, et al.
Published: (2024)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
by: Yan, Shuyi
Published: (2025)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
by: Zhao, Jingyang, et al.
Published: (2023)

Faster Algorithms for Graph Monopolarity
by: Philip, Geevarghese, et al.
Published: (2024)

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)

Faster Goal-Oriented Shortest Path Search for Bulk and Incremental Detailed Routing
by: Ahrens, Markus, et al.
Published: (2021)