I/O-complexity of graph algorithms

Conference Paper

We show lower bounds of Ω(E/V Sort(V)) for the I/O-complexity of graph theoretic problems like connected components, biconnected components, and minimum spanning trees, where E and V are the number of edges and vertices in the input graph, respectively. We also present a deterministic O(E/V Sort(V)·max(1, log log VBD/E)) algorithm for the problem of graph connectivity, where B and D denote respectively the block size and number of disks. Our algorithm includes a breadth first search; this maybe of independent interest.

Duke Authors

Cited Authors

  • Munagala, K; Ranade, A

Published Date

  • January 1, 1999

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 687 - 694

Citation Source

  • Scopus