I/O-complexity of graph algorithms
Publication
, Conference
Munagala, K; Ranade, A
Published in: Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
January 1, 1999
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 Scholars
Published In
Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
Publication Date
January 1, 1999
Start / End Page
687 / 694
Citation
APA
Chicago
ICMJE
MLA
NLM
Munagala, K., & Ranade, A. (1999). I/O-complexity of graph algorithms. In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (pp. 687–694).
Munagala, K., and A. Ranade. “I/O-complexity of graph algorithms.” In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, 687–94, 1999.
Munagala K, Ranade A. I/O-complexity of graph algorithms. In: Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. 1999. p. 687–94.
Munagala, K., and A. Ranade. “I/O-complexity of graph algorithms.” Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, 1999, pp. 687–94.
Munagala K, Ranade A. I/O-complexity of graph algorithms. Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. 1999. p. 687–694.
Published In
Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
Publication Date
January 1, 1999
Start / End Page
687 / 694