ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Algorithm 360: shortest-path forest with topological ordering [H]
Full text PdfPdf (693 KB)
Source
Communications of the ACM archive
Volume 12 ,  Issue 11  (November 1969) table of contents
Pages: 632 - 633  
Year of Publication: 1969
ISSN:0001-0782
Author
Robert B. Dial  Alan M. Voorhees and Associates, Inc., McLean, VA and Univ. of Washington, Seattle
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 32,   Downloads (12 Months): 131,   Citation Count: 31
Additional Information:

cited by   index terms  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/363269.363610
What is a DOI?

CITED BY  31
Andrew V. Goldberg, Scaling algorithms for the shortest paths problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.222-231, January 25-27, 1993, Austin, Texas, United States
Boris V. Cherkassky , Andrew V. Goldberg , Tomasz Radzik, Shortest paths algorithms: theory and experimental evaluation, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.516-525, January 23-25, 1994, Arlington, Virginia, United States
Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998
U. Pape, Algorithm 562: Shortest Path Lengths [H], ACM Transactions on Mathematical Software (TOMS), v.6 n.3, p.450-455, Sept. 1980
P. Klein , C. Stein , É. Tardos, Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.310-321, May 13-17, 1990, Baltimore, Maryland, United States
Zvi Galil , Xiangdong Yu, Short length versions of Menger's theorem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.499-508, May 29-June 01, 1995, Las Vegas, Nevada, United States
Stefan Edelkamp , Alberto Lluch Lafuente , Stefan Leue, Directed explicit model checking with HSF-SPIN, Proceedings of the 8th international SPIN workshop on Model checking of software, p.57-79, May 2001, Toronto, Ontario, Canada
Boris V. Cherkassky , Andrew V. Goldberg , Craig Silverstein, Buckets, heaps, lists, and monotone priority queues, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.83-92, January 05-07, 1997, New Orleans, Louisiana, United States
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
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
Richard Cole , Moshe Lewenstein, Multidimensional matching and fast search in suffix trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
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
Stefan Edelkamp , Stefan Schrödl, Route planning and map inference with global positioning traces, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003
U. Meyer , P. Sanders, Δ-stepping: a parallelizable shortest path algorithm, Journal of Algorithms, v.49 n.1, p.114-152, 1 October 2003
Ravindra K. Ahuja , Kurt Mehlhorn , James Orlin , Robert E. Tarjan, Faster algorithms for the shortest path problem, Journal of the ACM (JACM), v.37 n.2, p.213-223, April 1990
Alexandre X. Falcão , Jorge Stolfi , Roberto de Alencar Lotufo, The Image Foresting Transform: Theory, Algorithms, and Applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.1, p.19-29, January 2004
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
László G. Nyúl , Alexandre X. Falcão , Jayaram K. Udupa, Fuzzy-connected 3D image segmentation at interactive speeds, Graphical Models, v.64 n.5, p.259-281, September 2002
L. Fu , D. Sun , L. R. Rilett, Heuristic shortest path algorithms for transportation applications: state of the art, Computers and Operations Research, v.33 n.11, p.3324-3343, November 2006
Martin Holzer , Frank Schulz , Dorothea Wagner , Thomas Willhalm, Combining speed-up techniques for shortest-path computations, Journal of Experimental Algorithmics (JEA), 10, 2005
Ernesto Coto , Sören Grimm , David Williams, Technical Section: O-Buffer based IFT watershed from markers for large medical datasets, Computers and Graphics, v.31 n.6, p.848-863, December, 2007
Ricardo Fabbri , Luciano Da F. Costa , Julio C. Torelli , Odemir M. Bruno, 2D Euclidean distance transform algorithms: A comparative survey, ACM Computing Surveys (CSUR), v.40 n.1, p.1-44, February 2008
Hazem El-Alfy , David Jacobs , Larry Davis, Multi-scale video cropping, Proceedings of the 15th international conference on Multimedia, September 25-29, 2007, Augsburg, Germany
Julie Anne Cain , Peter Sanders , Nick Wormald, The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.469-476, January 07-09, 2007, New Orleans, Louisiana
Xue Bai , Guillermo Sapiro, Geodesic Matting: A Framework for Fast Interactive Image and Video Segmentation and Matting, International Journal of Computer Vision, v.82 n.2, p.113-132, April 2009
M. Sugie , O. Menzilcioglu , H. T. Kung, CARGuide: on-board computer for automobile route guidance, Proceedings of the July 9-12, 1984, national computer conference and exposition, July 09-12, 1984, Las Vegas, Nevada
Jun Yang , Min Zhang , Bo He , Chao Yang, Bi-level programming model and hybrid genetic algorithm for flow interception problem with customer choice, Computers & Mathematics with Applications, v.57 n.11-12, p.1985-1994, June, 2009
Stefan Edelkamp, Taming numbers and durations in the model checking integrated planning system, Journal of Artificial Intelligence Research, v.20 n.1, p.195-238, December 2003
Stefan Schroedl, An improved search algorithm for optimal multiple-sequence alignment, Journal of Artificial Intelligence Research, v.23 n.1, p.587-623, January 2005
Rüdiger Ebendt , Rolf Drechsler, Weighted A∗ search -- unifying view and application, Artificial Intelligence, v.173 n.14, p.1310-1342, September, 2009
Hsun-Jung Cho , Chien-Lun Lan, Hybrid shortest path algorithm for vehicle navigation, The Journal of Supercomputing, v.49 n.2, p.234-247, August 2009

INDEX TERMS

Keywords:
directed graph, network, shortest path, tree


The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player