TY - JFULL
AU - Udaya Kumar Reddy K. R and K. Viswanathan Iyer
PY - 2009/3/
TI - All-Pairs Shortest-Paths Problem for Unweighted Graphs in O(n2 log n) Time
T2 - International Journal of Computer and Information Engineering
SP - 319
EP - 326
VL - 3
SN - 1307-6892
UR - https://publications.waset.org/pdf/8870
PU - World Academy of Science, Engineering and Technology
NX - Open Science Index 26, 2009
N2 - Given a simple connected unweighted undirected graph G = (V (G), E(G)) with |V (G)| = n and |E(G)| = m, we present a new algorithm for the all-pairs shortest-path (APSP) problem. The running time of our algorithm is in O(n2 log n). This bound is an improvement over previous best known O(n2.376) time bound of Raimund Seidel (1995) for general graphs. The algorithm presented does not rely on fast matrix multiplication. Our algorithm with slight modifications, enables us to compute the APSP problem for unweighted directed graph in time O(n2 log n), improving a previous best known O(n2.575) time bound of Uri Zwick (2002).
ER -