CaltechAUTHORS
  A Caltech Library Service

Distributed computation on graphs: shortest path algorithms

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. 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:
URLURL TypeDescription
https://doi.org/10.1145/358690.358717DOIArticle
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:
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)81-0205
Subject Keywords:distributed computation, shortest path, negative cycle, depth first search, diffusing computation
Issue or Number:11
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:03 Oct 2019 20:42

Repository Staff Only: item control page