An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem

DOI10.1137/S0097539704441058MaRDI QIDQ3434993zbMATH OpenFDO

Authors Michael Elkin

Publication date 3 May 2007

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539704441058

zbMATH Keywords

distributed algorithmshardness of approximationminimum spanning tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Recommendations

• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• Distributed verification and hardness of distributed approximation
• Distributed verification and hardness of distributed approximation
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction

Cited in

(26)

• On efficient distributed construction of near optimal routing schemes
• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Fast distributed approximation for TAP and 2-edge-connectivity
• Approximate minimum directed spanning trees under congestion
• Latency, capacity, and distributed minimum spanning trees
• Low-congestion shortcut and graph parameters
• Message lower bounds via efficient network synchronization
• Low-congestion shortcuts without embedding
• A distributed algorithm for directed minimum-weight spanning tree
• Message Lower Bounds via Efficient Network Synchronization
• Fast distributed approximation for TAP and 2-edge-connectivity
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Distributed spanner approximation
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model
• Randomized Lower Bound for Distributed Spanning-Tree Verification
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Minimum cost flow in the CONGEST model
• Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
• Spanner approximations in practice
• Computing minimum weight cycle in the CONGEST model
• Polylogarithmic time algorithms for shortest path forests in programmable matter
• Polylogarithmic time algorithms for shortest path forests in programmable matter

This page was built for publication: An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem

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