Cover Image

$O(1)$-Round MPC Algorithms for Multi-dimensional Grid Graph Connectivity, EMST and DBSCAN

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gan, Junhao, Wirth, Anthony, Zhang, Zhuo
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity Computational Geometry Distributed, Parallel, and Cluster Computing
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Distributed Triangle Detection is Hard in Few Rounds
by: Assadi, Sepehr, et al.
Published: (2025)

Distributed-Memory Parallel Algorithms for Fixed-Radius Near Neighbor Graph Construction
by: Raulet, Gabriel, et al.
Published: (2025)

It's Hard to HAC with Average Linkage!
by: Bateni, MohammadHossein, et al.
Published: (2024)

Segmented Operations using Matrix Multiplications
by: Sobczyk, Aleksandros, et al.
Published: (2025)

Parallel Hierarchical Agglomerative Clustering in Low Dimensions
by: Bateni, MohammadHossein, et al.
Published: (2025)

Testing Spreading Behavior in Networks with Arbitrary Topologies
by: Modanese, Augusto, et al.
Published: (2023)

Work-Efficient Parallel Counting via Sampling
by: Liu, Hongyang, et al.
Published: (2024)

Round and Communication Efficient Graph Coloring
by: Chang, Yi-Jun, et al.
Published: (2024)

Fully Scalable MPC Algorithms for Euclidean k-Center
by: Czumaj, Artur, et al.
Published: (2025)

Fully Scalable MPC Algorithms for Clustering in High Dimension
by: Czumaj, Artur, et al.
Published: (2023)

To Store or Not to Store: a graph theoretical approach for Dataset Versioning
by: Guo, Anxin, et al.
Published: (2024)

Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion
by: Lenzen, Christoph, et al.
Published: (2024)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
by: Lingas, Andrzej
Published: (2026)

Improved Massively Parallel Triangle Counting in $O(1)$ Rounds
by: Liu, Quanquan C., et al.
Published: (2024)

Round-Delayed Amnesiac Flooding
by: Alafin, Oluwatobi, et al.
Published: (2026)

Distributed Santa Claus via Global Rounding
by: de Vos, Tijn, et al.
Published: (2026)

Sorting in One and Two Rounds using $t$-Comparators
by: Gelles, Ran, et al.
Published: (2024)

Lagrangian Simulation Volume-Based Contour Tree Simplification
by: Dilys, Domantas, et al.
Published: (2025)

A Surprisingly Simple Method for Distributed Euclidean-Minimum Spanning Tree / Single Linkage Dendrogram Construction from High Dimensional Embeddings via Distance Decomposition
by: Lettich, Richard
Published: (2024)

Extremely Scalable Distributed Computation of Contour Trees via Pre-Simplification
by: Li, Mingzhe, et al.
Published: (2025)

Composable Coresets for Constrained Determinant Maximization and Beyond
by: Mahabadi, Sepideh, et al.
Published: (2022)

Distributed Stochastic Graph Algorithms
by: Censor-Hillel, Keren, et al.
Published: (2026)

Distributed Graph Algorithms with Predictions
by: Boyar, Joan, et al.
Published: (2025)

Model-Agnostic Approximation of Constrained Forest Problems
by: Coupette, Corinna, et al.
Published: (2024)

What Can We Compute in a Single Round of the Congested Clique?
by: Robinson, Peter
Published: (2022)

PASGAL: Parallel And Scalable Graph Algorithm Library
by: Dong, Xiaojun, et al.
Published: (2024)

Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
by: Khoury, Seri, et al.
Published: (2025)

Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs
by: Akker, Erik van den, et al.
Published: (2024)

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
by: Bonamy, Marthe, et al.
Published: (2025)

Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice
by: Cai, Guangya
Published: (2025)

Engineering A Workload-balanced Push-Relabel Algorithm for Massive Graphs on GPUs
by: Hsieh, Chou-Ying, et al.
Published: (2024)

Fast Broadcast in Highly Connected Networks
by: Chandra, Shashwat, et al.
Published: (2024)

Informative Trains: A Memory-Efficient Journey to a Self-Stabilizing Leader Election Algorithm in Anonymous Graphs
by: Blin, Lelia, et al.
Published: (2026)

A Tight Lower Bound for 3-Coloring Grids in the Online-LOCAL Model
by: Chang, Yi-Jun, et al.
Published: (2023)

Restructuring expression dags for efficient parallelization
by: Wilhelm, Martin
Published: (2018)

Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model
by: Robinson, Peter, et al.
Published: (2025)

DAG-Inducing Problems and Algorithms
by: Gupta, Arya Tanmay, et al.
Published: (2023)

Eventually Lattice-Linear Algorithms
by: Gupta, Arya Tanmay, et al.
Published: (2023)

Parallel Algorithms for Hierarchical Nucleus Decomposition
by: Shi, Jessica, et al.
Published: (2023)

Encoding Schemes for Parallel In-Place Algorithms
by: Hutton, Chase, et al.
Published: (2025)