Loading...
Please wait, while we are loading the content...
Similar Documents
A blocked all-pairs shortest-paths algorithm
| Content Provider | ACM Digital Library |
|---|---|
| Author | Venkataraman, Gayathri Sahni, Sartaj Mukhopadhyaya, Srabani |
| Copyright Year | 2003 |
| Abstract | We propose a blocked version of Floyd's all-pairs shortest-paths algorithm. The blocked algorithm makes better utilization of cache than does Floyd's original algorithm. Experiments indicate that the blocked algorithm delivers a speedup (relative to the unblocked Floyd's algorithm) between 1.6 and 1.9 on a Sun Ultra Enterprise 4000/5000 for graphs that have between 480 and 3200 vertices. The measured speedup on an SGI O2 for graphs with between 240 and 1200 vertices is between 1.6 and 2. |
| File Format | |
| ISSN | 10846654 |
| e-ISSN | 10846654 |
| DOI | 10.1145/996546.996553 |
| Journal | Journal of Experimental Algorithmics (JEA) |
| Volume Number | 8 |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2003-12-01 |
| Publisher Place | New York |
| Access Restriction | One Nation One Subscription (ONOS) |
| Subject Keyword | All pairs shortest paths Blocking Cache Speedup |
| Content Type | Text |
| Resource Type | Article |
| Subject | Theoretical Computer Science |
