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)

zbMATH Keywords

minimum spanning treedistributed algorithmshardness of approximation

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

(22)

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

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)