Efficient parallel shortest-paths in digraphs with a separator decomposition

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient parallel shortest-paths in digraphs with a separator decomposition

Full text

Pdf (1.21 MB)

Source

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

Velen, Germany

Pages: 57 - 67

Year of Publication: 1993

ISBN:0-89791-599-2

Author

Edith Cohen

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 46, Citation Count: 2

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/165231.165240 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.

	1	Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
	2	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	3	Hristo N. Djidjev , Grammati E. Pantziou , Christos D. Zaroliagis, Computing shortest paths and distances in planar graphs, Proceedings of the 18th international colloquium on Automata, languages and programming, p.327-338, June 1991, Madrid, Spain
	4	Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
	5	Greg N. Frederickson, Planar graph decomposition and all pairs shortest paths, Journal of the ACM (JACM), v.38 n.1, p.162-204, Jan. 1991 [doi>10.1145/102782.102788]
	6	H. Gazit and G. L. Miller. A deterministic parallel algorithm for find#g a separator in planar graphs. Technical Report CMU-CS-91-103, Carnegle-Mellon University, 1991.
	7	Y. Han , V. Pan , John Reif, Efficient parallel algorithms for computing all pair shortest paths in directed graphs, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.353-362, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141913]
	8	J. J~J~. Parallel algorithms. Addison-Wesley Publishing Co., Reading, MA, 1992.
	9	M.-Y. Kao , P. N. Klein, Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.181-192, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100237]
	10	M.-Y. Kao , G. E. Shannon, Local reorientation, global order, and planar topology, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.286-296, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73034]
	11	P. N. Klein and S. Sairam. A parallel approximation scheme for planar shortest paths. Manuscript, 1993.
	12	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
	13	R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Applied Math., 36:177-189, 1979.
	14	Gary L. Miller , Shang-Hua Teng , Stephen A. Vavasis, A unified geometric approach to graph separators, Proceedings of the 32nd annual symposium on Foundations of computer science, p.538-547, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185417]
	15	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]
	16	V. Pan and J. Reif. The parallel computation of minimum cost paths in graphs by stream contraction. Information Processln9 Let., 40:79--83, 1991.
	17	Grammati E. Pantziou , Paul G. Spirakis , Christos D. Zaroliagis, Efficient parallel algorithms for shortest paths in planar digraphs, BIT, v.32 n.2, p.215-236, 1992 [doi>10.1007/BF01994878]

CITED BY 2

	Edith Cohen, Polylog-time and near-linear work approximation scheme for undirected shortest paths, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.16-26, May 23-25, 1994, Montreal, Quebec, Canada
	Philip Klein , Satish Rao , Monika Rauch , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.27-37, May 23-25, 1994, Montreal, Quebec, Canada