Two algorithms for shortest-paths problems in edge-weighted directed graphs

DOI10.1016/J.TCS.2026.115909MaRDI QIDQ7238537zbMATH OpenFDO

Authors Andrzej Lingas, Mia Persson, Dzmitry Sledneu

Publication date 8 May 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115909

zbMATH Keywords

all-pairs shortest paths problem (APSP)directed acyclic graph (DAG)edge-weighted directed graphsingle-source shortest paths problem (SSSP)time complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A new approach to all-pairs shortest paths on real-weighted graphs
• A note on two problems in connexion with graphs
• All pairs lightest shortest paths
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-pairs shortest paths and the essential subgraph
• An algorithm for finding shortest routes from all source nodes to a given destination in general networks
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Efficient determination of the transitive closure of a directed graph
• Faster all-pairs shortest paths via circuit complexity
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1875406 (Why is no real title available?)
• Introduction to algorithms.
• On a routing problem
• Subcubic equivalences between path, matrix, and triangle problems
• Topological sorting of large networks

This page was built for publication: Two algorithms for shortest-paths problems in edge-weighted directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7238537)