Cover Image

Log Diameter Rounds MST Verification and Sensitivity in MPC

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Coy, Sam, Czumaj, Artur, Mishra, Gopinath, Mukherjee, Anish
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Streaming Graph Algorithms in the Massively Parallel Computation Model
by: Czumaj, Artur, et al.
Published: (2025)

On Parallel $k$-Center Clustering
by: Coy, Sam, et al.
Published: (2023)

Optimal (degree+1)-Coloring in Congested Clique
by: Coy, Sam, et al.
Published: (2023)

Parallel Derandomization for Coloring
by: Coy, Sam, et al.
Published: (2023)

Property Testing of Computational Networks
by: Czumaj, Artur, et al.
Published: (2025)

Testing Depth First Search Numbering
by: Czumaj, Artur, et al.
Published: (2025)

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)

Streaming Algorithms for Geometric Steiner Forest
by: Czumaj, Artur, et al.
Published: (2020)

Round-efficient Fully-scalable MPC algorithms for k-Means
by: Jiang, Shaofeng H. -C., et al.
Published: (2026)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
by: Bishnu, Arijit, et al.
Published: (2025)

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

Near Uniform Triangle Sampling Over Adjacency List Graph Streams
by: Bishnu, Arijit, et al.
Published: (2024)

Modeling Online Paging in Multi-Core Systems
by: Mari, Mathieu, et al.
Published: (2024)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
by: Haeupler, Bernhard, et al.
Published: (2025)

Faster Semi-streaming Matchings via Alternating Trees
by: Mitrović, Slobodan, et al.
Published: (2024)

The Complexity Landscape of Dynamic Distributed Subgraph Finding
by: Chang, Yi-Jun, et al.
Published: (2024)

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
by: Chakraborty, Sourav, et al.
Published: (2024)

Diameter Computation on (Random) Geometric Graphs
by: Bläsius, Thomas, et al.
Published: (2026)

Going Beyond Surfaces in Diameter Approximation
by: Włodarczyk, Michał
Published: (2025)

Fault-Tolerant ST-Diameter Oracles
by: Bilò, Davide, et al.
Published: (2023)

Streaming Diameter of High-Dimensional Points
by: Halldórsson, Magnús M., et al.
Published: (2025)

Diameter Shortcut Sets on Temporal Graphs
by: Quantmeyer, Gerome
Published: (2025)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
by: Xu, Chao, et al.
Published: (2026)

Simpler and Faster Directed Low-Diameter Decompositions
by: Li, Jason
Published: (2025)

Constant-Stretch Rounding on the Hypersimplex
by: Anari, Nima, et al.
Published: (2026)

Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models
by: Bishnu, Arijit, et al.
Published: (2025)

New Diameter Approximations via Distance Oracle Techniques
by: Kirkpatrick, Yael, et al.
Published: (2026)

Sorting and Selection in Rounds with Adversarial Comparisons
by: Trevisan, Chris
Published: (2023)

Maximal Palindromes in MPC: Simple and Optimal
by: Pissis, Solon P.
Published: (2025)

Randomized Rounding over Dynamic Programs
by: Bamas, Etienne, et al.
Published: (2025)

Cut-Query Algorithms with Few Rounds
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
by: Banihashem, Kiarash, et al.
Published: (2025)

A Note on Rounding Matchings in General Graphs
by: Dudeja, Aditi
Published: (2024)

Proportionally Fair Matching via Randomized Rounding
by: Duppala, Sharmila, et al.
Published: (2024)

Online Rounding Schemes for $ k $-Rental Problems
by: Nekouyan, Hossein, et al.
Published: (2025)

Cost Preserving Dependent Rounding for Allocation Problems
by: Rohwedder, Lars, et al.
Published: (2025)

$k$-Clustering via Iterative Randomized Rounding
by: Byrka, Jarosław, et al.
Published: (2026)