Recent results on the single-source shortest paths problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Recent results on the single-source shortest paths problem

Full text

Pdf (419 KB)

Source

ACM SIGACT News archive
Volume 28 , Issue 2 (June 1997) table of contents

Pages: 81 - 87

Year of Publication: 1997

ISSN:0163-5700

Author

Rajeev Raman

Department of Computer Science, King's College London, Strand, London WC2R 2LS, UK

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 25, Citation Count: 13

Additional Information:

abstract cited by index terms collaborative colleagues

Tools and Actions:	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/261342.261352 What is a DOI?

ABSTRACT

We summarize the currently best known theoretical results for the single-source shortest paths problem for directed graphs with non-negative edge weights. We also point out that a recent result due to Cherkassky, Goldberg and Silverstein (1996) leads to even better time bounds for this problem than claimed by the authors.

CITED BY 13

	Seth Pettie , Vijaya Ramachandran, Computing shortest paths with comparisons and additions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.267-276, January 06-08, 2002, San Francisco, California
	Ulrich Meyer, Single-source shortest-paths on arbitrary directed graphs in linear average-case time, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.797-806, January 07-09, 2001, Washington, D.C., United States
	Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Ran Mendelson , Mikkel Thorup , Uri Zwick, Meldable RAM priority queues and minimum directed spanning trees, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999
	Ulrich Meyer, Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds, Journal of Algorithms, v.48 n.1, p.91-134, August 2003
	Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Journal of Computer and System Sciences, v.69 n.3, p.330-353, November 2004
	Daniele Frigioni , Mario Ioffreda , Umberto Nanni , Giulio Pasqualone, Experimental analysis of dynamic algorithms for the single, Journal of Experimental Algorithmics (JEA), 3, p.5-es, 1998
	Nighat Yasmin, Incremental computation of shortest paths in semi-dynamic graphs using software components, Proceedings of the 44th annual southeast regional conference, March 10-12, 2006, Melbourne, Florida
	Mattias Andersson , Joachim Gudmundsson , Christos Levcopoulos, Approximate distance oracles for graphs with dense clusters, Computational Geometry: Theory and Applications, v.37 n.3, p.142-154, August, 2007
	Cenk Çalışkan, A double scaling algorithm for the constrained maximum flow problem, Computers and Operations Research, v.35 n.4, p.1138-1150, April, 2008
	David Eppstein , Michael T. Goodrich , Darren Strash, Linear-time algorithms for geometric graphs with sublinearly many crossings, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.150-159, January 04-06, 2009, New York, New York
	David Eppstein , Michael T. Goodrich, Studying (non-planar) road networks through an algorithmic lens, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California