Log-diameter MST verification and sensitivity in MPC

DOI10.1007/S00453-025-01332-WMaRDI QIDQ6917983zbMATH OpenFDO

Authors Artur Czumaj, Gopinath Mishra, A. Mukherjee

Publication date 10 October 2025

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-025-01332-W

zbMATH Keywords

minimum spanning treeMPCsensitivityverification

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cites work

• A deterministic algorithm for the MST problem in constant rounds of congested clique
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• A randomized linear-time algorithm to find minimum spanning trees
• A simpler minimum spanning tree verification algorithm
• Algorithms and Computation
• An optimal EREW PRAM algorithm for minimum spanning tree verification
• An optimal minimum spanning tree algorithm
• Deterministic massively parallel connectivity
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• Log diameter rounds algorithms for 2-vertex and 2-edge connectivity
• MST in \(O(1)\) rounds of congested clique
• Near-optimal massively parallel graph connectivity
• On the History of the Minimum Spanning Tree Problem
• Optimal deterministic massively parallel connectivity on forests
• Optimal parallel verification of minimum spanning trees in logarithmic time
• Parallel graph connectivity in log diameter rounds
• Sorting, searching, and simulation in the MapReduce framework
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time

This page was built for publication: Log-diameter MST verification and sensitivity in MPC

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6917983)