Thumbnail
Access Restriction
Subscribed

Author Cohen, Edith
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2000
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than their sequential counterparts. This gap, known in the literature as the “transitive closure bottleneck,” poses a long-standing open problem. Our main result is an O<fen $lp="par">mn^{e0}+s<fen$ lp="par"> $m+n^{1+e0}<rp$ post="par"><rp post="par"> where $ε=\textit{O}(1/polylog$ $\textit{n})$ and $\textit{d}=\textit{O}(polylog$ $\textit{n}).$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2000-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 47
Issue Number 1
Page Count 35
Starting Page 132
Ending Page 166


Open content in new tab

   Open content in new tab
Source: ACM Digital Library