ICAR Research Data Repository for Knowledge Management
DSpace at IIT Bombay
View Archive InfoMetadata
| Field | Value |
| Title | A lower bound for the shortest path problem |
| Names |
MULMULEY, K
SHAH, P |
| Date Issued | 2001 (iso8601) |
| Abstract | We show that the shortest path problem cannot be solved in o(log n) time on an unbounded fan-in PRAM without bit operations using poly(n) processors, even when the bit-lengths of the weights on the edges are restricted to be of size O(log(3) n). This shows that the matrix-based repeated squaring algorithm for the shortest path problem is optimal in the unbounded fan-in PRAM model without bit operations. (C) 2001 Academic Press. |
| Genre | Article; Proceedings Paper |
| Identifier | JOURNAL OF COMPUTER AND SYSTEM SCIENCES,63(2)253-267 |