Polylog-time and near-linear work approximation scheme for undirected shortest paths

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Polylog-time and near-linear work approximation scheme for undirected shortest paths

Full text

Pdf (1.07 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 16 - 26

Year of Publication: 1994

ISBN:0-89791-663-8

Author

Edith Cohen

AT&T Bell Laboratories, Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/195058.195089 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	B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Nearlinear cost sequential and distributed constructions of sparse neighborhood covers. In Proc. 3#th IEEE Annual Symposium on Foundations of Computer Science, pages 638-647. IEEE, 1993.
	2	B. Awerbuch and D. Peleg. Sparse partitions. In Proc. 31st IEEE Annual Symposium on Foundations o} Computer Science, pages 503-513. IEEE, 1990.
	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 [doi>10.1145/165231.165240]
	4	E. Cohen. Fast algorithms for t-spanners and stretch-t paths. In Proc. 34th IEEE Annual Symposium on Foundations o} Computer Science, pages 648-658. IEEE, 1993.
	5	E. Cohen. Using selective path-doublingfor parallelshortestpath computations. In Proc. o} the 2nd Israeli Symposium on the Theory of Computing and Systems, pages 78-87. IEEE, 1993. full version submitted.
	6	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	7	P. N. Klein. A parallel randomized approximation scheme for shortest paths. Draft of journal version, 1992.
	8	Philip N. Klein , S. Sairam, A parallel randomized approximation scheme for shortest paths, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.750-758, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129785]
	9	P. N. Klein and S. Sairam. A linear-processor polylog-time algorithm for shortest paths in planar graphs, in Proc. 34th IEEE Annual Symposium on Foundations of Computer Science, pages 259-270. IEEE, 1993.
	10	Thomas H. Spencer, More time-work tradeoffs for parallel graph algorithms, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.81-93, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113387]
	11	Jeffrey D. Ullman , Mihalis Yannakakis, High probability parallel transitive-closure algorithms, SIAM Journal on Computing, v.20 n.1, p.100-125, Feb. 1991 [doi>10.1137/0220006]

CITED BY 6

	Edith Cohen , Uri Zwick, All-pairs small-stretch paths, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.93-102, January 05-07, 1997, New Orleans, Louisiana, United States
	Michael Elkin, Computing almost shortest paths, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.53-62, August 2001, Newport, Rhode Island, United States
	Yosi Ben-Asher , Gadi Haber, Parallel Solutions of Simple Indexed Recurrence Equations, IEEE Transactions on Parallel and Distributed Systems, v.12 n.1, p.22-37, January 2001
	Béla Bollobás , Don Coppersmith , Michael Elkin, Sparse distance preservers and additive spanners, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Michael Elkin , Jian Zhang, Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Michael Elkin, Computing almost shortest paths, ACM Transactions on Algorithms (TALG), v.1 n.2, p.283-323, October 2005