Creat membership Creat membership
Sign in

Forgot password?

Confirm
  • Forgot password?
    Sign Up
  • Confirm
    Sign In
Creat membership Creat membership
Sign in

Forgot password?

Confirm
  • Forgot password?
    Sign Up
  • Confirm
    Sign In
Collection

toTop

If you have any feedback, Please follow the official account to submit feedback.

Turn on your phone and scan

home > search >

Author:
Galil, Z  Margalit, O  


Journal:
INFORMATION AND COMPUTATION


Issue Date:
1997


Abstract(summary):

There is a way to transform the All Pairs Shortest Distances (APSD) problem where the edge lengths are integers with small (less than or equal to M) absolute value into a problem with edge lengths in {-1, 0, 1}. This transformation allows us to use the algorithms we developed earlier ([1]) and yields quite efficient algorithms. In this paper we give new improved algorithms for these problems. For n = \V\ the number of vertices, M the bound on edge length, and omega the exponent of matrix multiplication, we get the following results: 1. A directed nonnegative APSD(n, M) algorithm which runs in O(T(n, M)) time, where [GRAPHICS] 2. A undirected APSD(n, M) algorithm which runs in O(M(omega+1/2)n(omega) log(Mn)) time.


Page:
103---139


Similar Literature

Submit Feedback

This function is a member function, members do not limit the number of downloads