All pairs lightest shortest paths

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

All pairs lightest shortest paths

Full text

Pdf (659 KB)

Source

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

Atlanta, Georgia, United States

Pages: 61 - 69

Year of Publication: 1999

ISBN:1-58113-067-8

Author

Uri Zwick

Department of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 19, Citation Count: 4

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

	AGM97	Noga Alon , Zvi Galil , Oded Margalit, On the exponent of the all pairs shortest path problem, Journal of Computer and System Sciences, v.54 n.2, p.255-262, April 1997 [doi>10.1006/jcss.1997.1388]
	AHU74	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	AN96	N. Alon and M. Naor. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica, 16:434-449, 1996.
	CLR90	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	Cop97	Don Coppersmith, Rectangular matrix multiplication revisited, Journal of Complexity, v.13 n.1, p.42-49, March 1997 [doi>10.1006/jcom.1997.0438]
	CW90	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]
	Dij59	E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.
	FT87	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
	GM97a	Zvi Galil , Oded Margalit, All pairs shortest distances for graphs with small integer length edges, Information and Computation, v.134 n.2, p.103-139, May 1, 1997 [doi>10.1006/inco.1997.2620]
	GM97b	Zvi Galil , Oded Margalit, All pairs shortest paths for graphs with small integer length edges, Journal of Computer and System Sciences, v.54 n.2, p.243-254, April 1997 [doi>10.1006/jcss.1997.1385]
	HP98	Xiaohan Huang , Victor Y. Pan, Fast rectangular matrix multiplication and applications, Journal of Complexity, v.14 n.2, p.257-299, June 1, 1998 [doi>10.1006/jcom.1998.0476]
	Joh77	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]
	Sei95	Raimund Seidel, On the all-pairs-shortest-path problem in unweighted undirected graphs, Journal of Computer and System Sciences, v.51 n.3, p.400-403, Dec. 1995 [doi>10.1006/jcss.1995.1078]
	Tak98	T. Takaoka. Subcubic cost algorithms for the all pairs shortest path problem. AIgorithmica, 20:309-318, 1998.
	Zwi98	Uri Zwick, All Pairs Shortest Paths in weighted directed graphs ? exact and almost exact algorithms, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.310, November 08-11, 1998

CITED BY 4

	All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002
	Michael A. Bender , Giridhar Pemmasani , Steven Skiena , Pavel Sumazin, Finding least common ancestors in directed acyclic graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.845-854, January 07-09, 2001, Washington, D.C., United States
	Timothy M. Chan, More algorithms for all-pairs shortest paths in weighted graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Asaf Shapira , Raphael Yuster , Uri Zwick, All-pairs bottleneck paths in vertex weighted graphs, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.978-985, January 07-09, 2007, New Orleans, Louisiana