An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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