Efficient parallel algorithms for computing all pair shortest paths in directed graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient parallel algorithms for computing all pair shortest paths in directed graphs

Full text

Pdf (687 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures table of contents

San Diego, California, United States

Pages: 353 - 362

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

Y. Han
V. Pan
John Reif

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 77, Citation Count: 3

Additional Information:

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/140901.141913 What is a DOI?

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.

	AGM	Noga Alon , Zvi Galil , Oded Margalit, On the exponent of the all pairs shortest path problem, Proceedings of the 32nd annual symposium on Foundations of computer science, p.569-575, September 1991, San Juan, Puerto Rico
	Di	E.W. Dijkstra. A note on two problems in connextion with graphs. Numerische Mathematik 1,269-271, 1959.
	Fl	Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
	Fr	M.L. Fredman. New bounds on the complexity of the shortest p~th problem. SIAM J. Comput., Vol. 5, No. 1, 83- 89(March 1976).
	GM	Hillel Gazit , Gary L. Miller, An improved parallel algorithm that computes the BFS numbering of a directed graph, Information Processing Letters, v.28 n.2, p.61-65, June 24, 1988 [doi>10.1016/0020-0190(88)90164-0]
	J	Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
	KR	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	L	Andrzej Lingas, Efficient parallel algorithms for path problems in planar directed graphs, Proceedings of the international symposium on Algorithms, p.447-457, August 1990, Tokyo, Japan
	PK	It. C. Paige and C. P. Kruskal. Parallel algorithms for shortest path problems. Proc. 1985 Int. Conf. on Parallel Processing, St. Charles, Illinois, 14-19.
	PP	V.Y. Pan and F.P. Preparata. Supereffective slow-down of parallel algorithms. Manuscript, 1991.
	PR1	V. Pan , J. Reif, Fast and efficient solution of path algebra problems, Journal of Computer and System Sciences, v.38 n.3, p.494-510, June 1989 [doi>10.1016/0022-0000(89)90013-5]
	PR2	V. Pan and J. H. Reif. The parallel computation of minimum cost paths in graphs by stream contraction. Information Processing Letters 40, 79-83, 1991.
	R	R. tteischuk. Probabilistic parallel algorithms for sorting and selection. SIAM J. Comput., Vol. 14, No. 2, 396-409(May 1985).
	S	R. Seidel. On the all-pair-shortest-path problem. Manuscript, 1991.
	V	L.G. Valiant. Parallelism in comparison problems. SIAM J. Comp., Vol. 4, No. 3, 348-355(Sept. 1975).

CITED BY 3

	Edith Cohen, Efficient parallel shortest-paths in digraphs with a separator decomposition, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.57-67, June 30-July 02, 1993, Velen, Germany
	Andy Yoo , Edmond Chow , Keith Henderson , William McLendon , Bruce Hendrickson , Umit Catalyurek, A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.25, November 12-18, 2005
	Bronis R. De Supinski , Martin Schulz , Vasily V. Bulatov , William Cabot , Bor Chan , Andrew W. Cook , Erik W. Draeger , James N. Glosli , Jeffrey A. Greenough , Keith Henderson , Alison Kubota , Steve Louis , Brian J. Miller , Mehul V. Patel , Thomas E. Spelce , Frederick H. Streitz , Peter L. Williams , Robert K. Yates , Andy Yoo , George Almasi , Gyan Bhanot , Alan Gara , John A. Gunnels , Manish Gupta , Jose Moreira , James Sexton , Bob Walkup , Charles Archer , Francois Gygi , Timothy C. Germann , Kai Kadau , Peter S. Lomdahl , Charles Rendleman , Michael L. Welcome , William Mclendon , Bruce Hendrickson , Franz Franchetti , Stefan Kral , Jürgen Lorenz , Christoph W. Überhuber , Edmond Chow , Ümit Çatalyürek, BlueGene/L applications: Parallelism On a Massive Scale, International Journal of High Performance Computing Applications, v.22 n.1, p.33-51, February 2008