Streaming Graph Algorithms in the Massively Parallel Computation Model
Abstract
References
Index Terms
- Streaming Graph Algorithms in the Massively Parallel Computation Model
Recommendations
Deterministic massively parallel connectivity
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of ComputingWe consider the problem of designing fundamental graph algorithms on the model of Massive Parallel Computation (MPC). The input to the problem is an undirected graph G with n vertices and m edges, and with D being the maximum diameter of any connected ...
On graph problems in a semi-streaming model
Automata, languages and programming: Algorithms and complexity (ICALP-A 2004)We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose edge sets cannot be stored in memory. In this model, ...
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O(log2 n) for ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
- Chair:
- Ran Gelles,
- Proceedings Chair:
- Dennis Olivetti,
- Program Chair:
- Petr Kuznetsov
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
Acceptance Rates
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 181Total Downloads
- Downloads (Last 12 months)181
- Downloads (Last 6 weeks)39
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in