Distributed computation on graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Distributed computation on graphs: shortest path algorithms

Full text

Pdf (393 KB)

Source

Communications of the ACM archive
Volume 25 , Issue 11 (November 1982) table of contents

Pages: 833 - 837

Year of Publication: 1982

ISSN:0001-0782

Authors

K. Mani Chandy	Univ. of Texas, Austin
J. Misra	Univ. of Texas, Austin

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 99, Citation Count: 26

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/358690.358717 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Dijkstra, E.W., and Scholten, C.S. Termination detection for diffusing computations. Inf. Process. Lett 11, (Aug. 1980), 1, 1-4.
	2	Ford, L.R., and Fulkerson, D.R. Flows in Networks. Princeton Univ. Press, Princeton, N. J., 1962.

CITED BY 26

	Mohan Sharma , Jianhua Chen , Sitharama Iyengar, Distributed algorithms for locating centers and medians in communication networks, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.808-817, March 1992, Kansas City, Missouri, United States
	Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984
	Juan Touriño , Francisco F. Rivera , Carlos Alvarez , César M. Dans , Jorge Parapar , Ramón Doallo , Marcos Boullón , Javier D. Bruguera , Rafael Crecente , Xesús P. González, COPA: a GIS-based tool for land consolidation projects, Proceedings of the 9th ACM international symposium on Advances in geographic information systems, November 09-10, 2001, Atlanta, Georgia, USA
	Azzedine Boukerche , Carl Tropper, SGTNE: semi-global time of the next event algorithm, ACM SIGSIM Simulation Digest, v.25 n.1, p.68-77, July 1995
	Paul T. R. Wang , William P. Niedringhaus, Distributed/parallel traffic simulation for IVHS applications, Proceedings of the 25th conference on Winter simulation, p.1225-1230, December 12-15, 1993, Los Angeles, California, United States
	Paul Hudak, Distributed task and memory management, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.277-289, August 17-19, 1983, Montreal, Quebec, Canada
	Jeffrey K. Hollingsworth, An online computation of critical path profiling, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.11-20, May 22-23, 1996, Philadelphia, Pennsylvania, United States
	J. J. Garcia-Lunes-Aceves, Loop-free routing using diffusing computations, IEEE/ACM Transactions on Networking (TON), v.1 n.1, p.130-141, Feb. 1993
	Jayadev Misra, Detecting termination of distributed computations using markers, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.290-294, August 17-19, 1983, Montreal, Quebec, Canada
	Jayadev Misra , K. M. Chandy, A Distributed Graph Algorithm: Knot Detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.678-686, Oct. 1982
	J. K. Hollingsworth , B. P. Miller, Parallel program performance metrics: a comprison and validation, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.4-13, November 16-20, 1992, Minneapolis, Minnesota, United States
	J. J. Garcia-Luna-Aceves, A unified approach to loop-free routing using distance vectors or link states, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.212-223, Sep. 1989
	Weifa Liang , Hong Shen, Multicast in large WDM networks, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
	U. Meyer , P. Sanders, Δ-stepping: a parallelizable shortest path algorithm, Journal of Algorithms, v.49 n.1, p.114-152, 1 October 2003
	D. Kumar, Development of a Class of Distributed Termination Detection Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.4 n.2, p.145-155, April 1992
	Mohamed G. Gouda , Marco Schneider, Maximizable routing metrics, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.663-675, August 2003
	K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985
	K. V. S. Ramarao, Distributed Algorithms for Network Recognition Problems, IEEE Transactions on Computers, v.38 n.9, p.1240-1248, September 1989
	B. P. Miller , M. Clark , J. Hollingsworth , S. Kierstead , S. S. Lim , T. Torzewski, IPS-2: The Second Generation of a Parallel Program Measurement System, IEEE Transactions on Parallel and Distributed Systems, v.1 n.2, p.206-217, April 1990
	Nicola Santoro, Sense of direction, topological awareness and communication complexity, ACM SIGACT News, v.16 n.2, p.50-56, Summer 1984
	Eoin A. O'Cearbhaill , Margaret O'Mahony, Parallel implementation of a transportation network model, Journal of Parallel and Distributed Computing, v.65 n.1, p.1-14, January 2005
	Azzedine Boukerche , Carl Tropper, Parallel simulation on the hypercube multiprocessor, Distributed Computing, v.8 n.4, p.181-190, June 1995
	K. B. Lakshmanan , K. Thulasiraman , M. A. Comeau, An Efficient Distributed Protocol for Finding Shortest Paths in Networks with Negative Weights, IEEE Transactions on Software Engineering, v.15 n.5, p.639-644, May 1989
	C.-Q. Yang , B. P. Miller, Performance Measurement for Parallel and Distributed Programs: a Structured and Automatic Approach, IEEE Transactions on Software Engineering, v.15 n.12, p.1615-1629, December 1989
	Paulius Micikevicius , Narsingh Deo, Cluster Computing for Determining Three-Dimensional Protein Structure, The Journal of Supercomputing, v.34 n.3, p.243-271, December 2005
	Weifa Liang , Xiaoxing Guo, Online Multicasting for Network Capacity Maximization in Energy-Constrained Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.9, p.1215-1227, September 2006