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
On external memory graph traversal
Full text PdfPdf (203 KB)
Source Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents
San Francisco, California, United States
Pages: 859 - 860  
Year of Publication: 2000
ISBN:0-89871-453-2
Authors
Adam L. Buchsbaum  AT&T Labs, Shannon Laboratory, 180 Park Ave., Florham Park, NJ
Michael Goldwasser  Dept. of Math and Comp. Science, Loyola University Chicago, 6525 N. Sheridan Rd., Chicago, IL and Princeton University
Suresh Venkatasubramanian  AT&T Labs, Shannon Laboratory, 180 Park Ave., Florham Park, NJ
Jeffery R. Westbrook  AT&T Labs, Shannon Laboratory, 180 Park Ave., Florham Park, NJ
Sponsors
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics
Publisher
Society for Industrial and Applied Mathematics  Philadelphia, PA, USA
Bibliometrics
Downloads (6 Weeks): 5,   Downloads (12 Months): 40,   Citation Count: 18
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Review this Article  

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
Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988  [doi>10.1145/48529.48535]
 
2
Lars Arge, The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.334-345, August 16-18, 1995
 
3
Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
 
4
Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
 
5
Kameshwar Munagala , Abhiram Ranade, I/O-complexity of graph algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.687-694, January 17-19, 1999, Baltimore, Maryland, United States
 
6
Vijay Kumar , Eric J. Schwabe, Improved Algorithms and Data Structures for Solving Graph Problems in External Memory, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.169, October 23-26, 1996

CITED BY  18
Jop F. Sibeyn , James Abello , Ulrich Meyer, Heuristics for semi-external depth first search on directed graphs, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001
Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
Jun-Ho Her , R. S. Ramakrishna, External-memory depth-first search algorithm for solid grid graphs, Information Processing Letters, v.93 n.4, p.177-183, 28 February 2005
Jeffrey Scott Vitter, External memory algorithms, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
Rezaul Alam Chowdhury , Vijaya Ramachandran, Cache-oblivious shortest paths in graphs using buffer heap, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
Lars Arge , Gerth Stølting Brodal , Laura Toma, On external-memory MST, SSSP and multi-way planar graph separation, Journal of Algorithms, v.53 n.2, p.186-206, November 2004
Lars Arge , Laura Toma , Norbert Zeh, I/O-efficient topological sorting of planar DAGs, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
Deepak Ajwani , Roman Dementiev , Ulrich Meyer, A computational study of external-memory BFS algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.601-610, January 22-26, 2006, Miami, Florida
Lars Arge , Laura Toma , Jeffrey Scott Vitter, I/O-Efficient Algorithms for Problems on Grid-Based Terrains, Journal of Experimental Algorithmics (JEA), 6, p.1-es, 2001
Lars Arge , Michael A. Bender , Erik D. Demaine , Bryan Holland-Minkley , J. Ian Munro, Cache-oblivious priority queue and graph algorithm applications, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Michael A. Bender , Martin Farach-Colton , Jeremy T. Fineman , Yonatan R. Fogel , Bradley C. Kuszmaul , Jelani Nelson, Cache-oblivious streaming B-trees, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
Jun-Ho Her , R. S. Ramakrishna, An external-memory depth-first search algorithm for general grid graphs, Theoretical Computer Science, v.374 n.1-3, p.170-180, April, 2007
Lintao Zhang , Sharad Malik, Validating SAT Solvers Using an Independent Resolution-Based Checker: Practical Implementations and Other Applications, Proceedings of the conference on Design, Automation and Test in Europe, p.10880, March 03-07, 2003
Jeffrey Scott Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, v.2 n.4, p.305-474, January 2008
Nilesh Bansal , Fei Chiang , Nick Koudas , Frank Wm. Tompa, Seeking stable clusters in the blogosphere, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
Bhavana Bharat Dalvi , Meghana Kshirsagar , S. Sudarshan, Keyword search on external memory data graphs, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
Ke Yi, Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  E. Data

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures


General Terms:
Algorithms, Design, Theory, Verification

Collaborative Colleagues:
Adam L. Buchsbaum: colleagues
Michael Goldwasser: colleagues
Suresh Venkatasubramanian: colleagues
Jeffery R. Westbrook: colleagues

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