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