A blocked all-pairs shortest-paths algorithm

DOI10.1145/996546.996553MaRDI QIDQ5463439zbMATH OpenOpenAlexFDO

Authors Gayathri Venkataraman, Srabani Mukhopadhyaya, Sartaj Sahni

Publication date 4 August 2005

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL http://www.acm.org/jea/2003/VenkataramanBlocked/

zbMATH Keywords

algorithmsall pairs shortest pathsblockingcachespeedup

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1617277
• Generalized blocked Floyd-Warshall algorithm
• scientific article; zbMATH DE number 278831
• scientific article; zbMATH DE number 219247
• Two fast algorithms for all-pairs shortest paths

Cites work

• A memetic algorithm to schedule planned maintenance for the national grid
• Analysing cache effects in distribution sorting
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 1305454 (Why is no real title available?)
• scientific article; zbMATH DE number 830949 (Why is no real title available?)
• Improving memory performance of sorting algorithms
• Irredundant intervals
• Organizing matrices and matrix operations for paged memory systems
• The Influence of Caches on the Performance of Sorting
• The uniform memory hierarchy model of computation

Cited in

(8)

• Shortest path and closure algorithms for banded matrices
• scientific article; zbMATH DE number 1617277 (Why is no real title available?)
• Generalized blocked Floyd-Warshall algorithm
• Improving the cache-efficiency of shortest path search
• Conditions for the existence of broadcast and spatial locality in computation threads
• Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem
• Heterogeneous blocked all-pairs shortest paths algorithm for clustered weighted graphs
• Solving path problems on the GPU

This page was built for publication: A blocked all-pairs shortest-paths algorithm

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