Sharing information for the all pairs shortest path problem

DOI10.1016/J.TCS.2013.09.006zbMath1358.05288OpenAlexW1980620373MaRDI QIDQ391758

Tadao Takaoka

Publication date: 13 January 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.09.006

zbMATH Keywords

priority queueinformation sharingall pairs shortest path problemlimited edge costnearly acyclic graphsingle sink shortest path problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Unnamed Item ⋮ Algebraic theory on shortest paths for all flows ⋮ Algebraic Theory on Shortest Paths for All Flows

Uses Software

• Algorithm 360

Cites Work

• A note on two problems in connexion with graphs
• Solving shortest paths efficiently on nearly acyclic directed graphs
• Shortest path algorithms for nearly acyclic directed graphs
• Improved shortest path algorithms for nearly acyclic graphs
• A new approach to all-pairs shortest paths on real-weighted graphs
• Shortest paths algorithms: Theory and experimental evaluation
• Faster algorithms for the shortest path problem
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• Fibonacci heaps and their uses in improved network optimization algorithms
• Integer priority queues with decrease key in constant time and the single source shortest paths problem

This page was built for publication: Sharing information for the all pairs shortest path problem