Chandy, K. M. and Misra, J. (1982) Distributed computation on graphs: shortest path algorithms. Communications of the ACM, 25 (11). pp. 833-837. ISSN 0001-0782. doi:10.1145/358690.358717. https://resolver.caltech.edu/CaltechAUTHORS:20190111-085547749
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190111-085547749
Abstract
We use the paradigm of diffusing computation, introduced by Dijkstra and Scholten, to solve a class of graph problems. We present a detailed solution to the problem of computing shortest paths from a single vertex to all other vertices, in the presence of negative cycles.
| Item Type: | Article | ||||||
|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||
| Additional Information: | © 1982 ACM. Received 7/80; revised 9/81; accepted 3/82. This work was supported in part by the Air Force Office of Scientific Research under grant AFOSR 81-0205. We are indebted to E. W. Dijkstra for his comments on an earlier draft of this paper; his suggestions led to more concise proofs in Section 5. We are also grateful to unknown referees and M. D. McIlroy for their suggestions and corrections. | ||||||
| Funders: |
| ||||||
| Subject Keywords: | distributed computation, shortest path, negative cycle, depth first search, diffusing computation | ||||||
| Issue or Number: | 11 | ||||||
| DOI: | 10.1145/358690.358717 | ||||||
| Record Number: | CaltechAUTHORS:20190111-085547749 | ||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190111-085547749 | ||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
| ID Code: | 92211 | ||||||
| Collection: | CaltechAUTHORS | ||||||
| Deposited By: | Tony Diaz | ||||||
| Deposited On: | 11 Jan 2019 17:48 | ||||||
| Last Modified: | 16 Nov 2021 03:48 |
Repository Staff Only: item control page
