scientific article; zbMATH DE number 7561284

DOI10.4230/LIPIcs.DISC.2018.32zbMath1497.68565arXiv1810.03513MaRDI QIDQ5090924

Gopal Pandurangan, Robert Gmyr

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1810.03513

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

MSTrandomized algorithmsparsifiersingular optimality

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Latency, capacity, and distributed minimum spanning trees ⋮ Communication costs in a geometric communication network ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ Low-congestion shortcut and graph parameters ⋮ Beep-and-sleep: message and energy efficient set cover ⋮ Beep-and-sleep: message and energy efficient set cover

Cites Work

• Unnamed Item
• Universal classes of hash functions
• Random Sampling in Cut, Flow, and Network Design Problems
• Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
• Toward Optimal Bounds in the Congested Clique
• Distributed Minimum Cut Approximation
• Randomized broadcast in networks
• A trade-off between information and communication in broadcast protocols
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Computing: A Locality-Sensitive Approach
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Distributed Verification and Hardness of Distributed Approximation
• All-Pairs Almost Shortest Paths
• A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
• A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
• Round- and Message-Optimal Distributed Graph Algorithms
• Distributed Computation of Large-scale Graph Problems
• Probability and Computing
• Almost-Tight Distributed Minimum Cut Algorithms
• On the Complexity of Universal Leader Election