A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths

A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths

0.00 Avg rating—0 Votes
Article ID: iaor20071430
Country: United States
Volume: 46
Issue: 2
Start Page Number: 181
End Page Number: 192
Publication Date: Oct 2006
Journal: Algorithmica
Authors:
Abstract:

We present an O(n3√(log log n)/logn)-time algorithm for the All Pairs Shortest Paths (APSP) problem for directed graphs with real edge lengths. This slightly improves previous algorithms for the problem obtained by Fredman, Dobosiewicz, Han, and Takaoka.

Reviews

Required fields are marked *. Your email address will not be published.