I/O-complexity of graph algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

I/O-complexity of graph algorithms

Full text

Pdf (913 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 687 - 694

Year of Publication: 1999

ISBN:0-89871-434-6

Authors

Kameshwar Munagala	Department of Computer Science, Stanford University, Stanford, CA and Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai 400076 India
Abhiram Ranade	Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai 400076 India

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): 11, Downloads (12 Months): 62, Citation Count: 25

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

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	Jeffery Vitter, and Elizabeth Shriver, Optimal Algo- Algorithmica 12(2-3), 1994, pp. 110-147.
	2	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
	3	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
	4	James Abello , Adam L. Buchsbaum , Jeffery Westbrook, A Functional Approach to External Graph Algorithms, Proceedings of the 6th Annual European Symposium on Algorithms, p.332-343, August 24-26, 1998
	5	Lars Arge , Mikael Knudsen , Kirsten Larsen, A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms, Proceedings of the Third Workshop on Algorithms and Data Structures, p.83-94, August 11-13, 1993
	6	Abhiram G. Ranade , Sandeep N. Bhatt , Lennart S. Johnsson, The fluent abstract machine, Proceedings of the fifth MIT conference on Advanced research in VLSI, p.71-93, January 1988, Cambridge, Massachusetts, United States
	7	Francis Y. Chin , John Lam , I-Ngo Chen, Efficient parallel algorithms for some graph problems, Communications of the ACM, v.25 n.9, p.659-665, Sept 1982 [doi>10.1145/358628.358650]
	8	Richard Cole , Uzi Vishkin, Approximate parallel scheduling. II.: applications to logarithmic-time optimal parallel graph algorithms, Information and Computation, v.92 n.1, p.1-47, May 1991 [doi>10.1016/0890-5401(91)90019-X]
	9	Lars Arge , Peter Bro Miltersen, On showing lower bounds for external-memory computational geometry problems, External memory algorithms, American Mathematical Society, Boston, MA, 1999
	10	Monica Henzinger, Prabhakar Raghavan, and Sridar Rajagopalan, Computing on Data Streams, SRC Teclxical Note 1998-011, Digital Systems Research Center.

CITED BY 25

	Ulrich Meyer, External memory BFS on undirected graphs with bounded degree, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.87-88, January 07-09, 2001, Washington, D.C., United States
	David Hutchinson , Anil Maheshwari , Norbert Zeh, An external memory data structure for shortest path queries, Discrete Applied Mathematics, v.126 n.1, p.55-82, March 2003
	Anil Maheshwari , Norbert Zeh, I/O-optimal algorithms for planar graphs using separators, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.372-381, January 06-08, 2002, San Francisco, California
	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
	Adam L. Buchsbaum , Michael Goldwasser , Suresh Venkatasubramanian , Jeffery R. Westbrook, On external memory graph traversal, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.859-860, January 09-11, 2000, San Francisco, California, United States
	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
	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
	Rezaul Alam Chowdhury , Vijaya Ramachandran, External-memory exact and approximate all-pairs shortest-paths in undirected graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Jeff Erickson, Lower bounds for external algebraic decision trees, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	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
	Luca Allulli , Peter Lichodzijewski , Norbert Zeh, A faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge lengths, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.910-919, January 07-09, 2007, New Orleans, Louisiana
	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
	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
	Richard E. Korf, Linear-time disk-based implicit graph search, Journal of the ACM (JACM), v.55 n.6, p.1-40, December 2008
	Rong Zhou , Eric A. Hansen, External-memory pattern databases using structured duplicate detection, Proceedings of the 20th national conference on Artificial intelligence, p.1398-1404, July 09-13, 2005, Pittsburgh, Pennsylvania
	Rong Zhou , Eric A. Hansen, Structured duplicate detection in external-memory graph search, Proceedings of the 19th national conference on Artifical intelligence, p.683-688, July 25-29, 2004, San Jose, California
	Yokesh Kumar , Prosenjit Gupta, External memory layout vs. schematic, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.2, p.1-20, March 2009
	Rong Zhou , Eric A. Hansen, Domain-independent structured duplicate detection, proceedings of the 21st national conference on Artificial intelligence, p.1082-1087, July 16-20, 2006, Boston, Massachusetts
	Stefan Edelkamp , Shahid Jabbar, Cost-optimal external planning, Proceedings of the 21st national conference on Artificial intelligence, p.821-826, July 16-20, 2006, Boston, Massachusetts
	Ariel Felner , Richard E. Korf , Ram Meshulam , Robert Holte, Compressed pattern databases, Journal of Artificial Intelligence Research, v.30 n.1, p.213-247, September 2007
	Rong Zhou , Eric A. Hansen, Edge partitioning in external-memory graph search, Proceedings of the 20th international joint conference on Artifical intelligence, p.2410-2416, January 06-12, 2007, Hyderabad, India