On the all-pairs-shortest-path problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the all-pairs-shortest-path problem

Full text

Pdf (404 KB)

Source

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

Victoria, British Columbia, Canada

Pages: 745 - 749

Year of Publication: 1992

ISBN:0-89791-511-9

Author

Raimund Seidel

Computer Science Division, University of California, Berkeley, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 34, Downloads (12 Months): 122, Citation Count: 11

Additional Information:

references cited by index terms review 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/129712.129784 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	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
	2	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]
	3	Tomás Feder , Rajeev Motwani, Clique partitions, graph compression and speeding-up algorithms, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.123-133, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103424]
	4	M. L. Fredman, New Bounds on the Complezity of the Shortest Path Problem, SIAM J. Comp. 5 (1976), 83- 89.
	5	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]
	6	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]
	7	Z. Galil, Private Communication.
	8	Z. Galil and O. Margalit, On the Exponent of the All Pairs Shortest Path Problem, Manuscript, April 1991.
	9	Harold N. Gabow, Scaling algorithms for network problems, Journal of Computer and System Sciences, v.31 n.2, p.148-168, Sept. 1985 [doi>10.1016/0022-0000(85)90039-X]
	10	D. R. Karger, Private Communication.
	11	David R. Karger , Daphne Koller , Steven J. Phillips, Finding the hidden path: time bounds for all-pairs shortest paths, Proceedings of the 32nd annual symposium on Foundations of computer science, p.560-568, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185419]
	12	C. C. McGeoch, Finding Shortest Paths with the Optimal Subgraph, Manuscript, 1992.
	13	Victor Pan, How to multiply matrices faster, Springer-Verlag New York, Inc., New York, NY, 1984
	14	F. Romani, Shortest-Path Problem is not Harder than Matrix Multiplication, IPL 11 (1980) 134-136.
	15	G. Yuval, An Algorithm for Finding All Shortest Paths Using NTM Infinite-Precision Multiplications, IPL 4 (1976) 155-156.

CITED BY 11

	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 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
	D. Aingworth , C. Chekuri , R. Motwani, Fast estimation of diameter and shortest paths (without matrix multiplication), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.547-553, January 28-30, 1996, Atlanta, Georgia, United States
	Madhumangal Pal , G. P. Bhattacharjee, An optimal parallel algorithm for all-pairs shortest paths on unweighted interval graphs, Nordic Journal of Computing, v.4 n.4, p.342-356, Winter 1997
	Anshul Gupta , Pankaj Rohatgi , Ramesh Agarwal, Fast practical algorithms for the Boolean-product-witness-matrix problem, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.146-152, July 2000, St. Andrews, Scotland
	Jop F. Sibeyn, External matrix multiplication and all-pairs shortest path, Information Processing Letters, v.91 n.2, p.99-106, 31 July 2004
	Feodor F. Dragan, Estimating all pairs shortest paths in restricted graph families: a unified approach, Journal of Algorithms, v.57 n.1, p.1-21, September 2005
	Virginia Vassilevska , Ryan Williams, Finding a maximum weight triangle in n^3-Δ time, with applications, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	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
	Monique V. Vieira , Bruno M. Fonseca , Rodrigo Damazio , Paulo B. Golgher , Davi de Castro Reis , Berthier Ribeiro-Neto, Efficient search ranking in social networks, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Clémence Magnien , Matthieu Latapy , Michel Habib, Fast computation of empirically tight bounds for the diameter of massive graphs, Journal of Experimental Algorithmics (JEA), 13, February 2009

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.2 Graph Theory
Subjects: Path and circuit problems

Additional Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.2 Modes of Computation
Subjects: Probabilistic computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

REVIEW

"Noga Alon : Reviewer"

An ingenious simple trick enables the author to improve a previous result of myself, Z. Galil, and O. Margalit [1] for an interesting special case. He obtains an algorithm that finds the distances between all pairs of vertices of an more...

Collaborative Colleagues:

Raimund Seidel: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player