An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs
From MaRDI portal
Publication:6102272
DOI10.1007/978-3-030-95018-7_12arXiv2108.03455OpenAlexW4226024673MaRDI QIDQ6102272
Andrzej Lingas, Mia Persson, Dzmitry Sledneu
Publication date: 8 May 2023
Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2108.03455
Cites Work
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- A new approach to all-pairs shortest paths on real-weighted graphs
- All-pairs shortest paths and the essential subgraph
- Efficient determination of the transitive closure of a directed graph
- All pairs lightest shortest paths
- On a routing problem
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
- Randomized Speedup of the Bellman–Ford Algorithm
- An algorithm for finding shortest routes from all source nodes to a given destination in general networks