Randomized Lower Bound for Distributed Spanning-Tree Verification

DOI10.1007/978-3-319-09620-9_12MaRDI QIDQ5496155zbMATH OpenOpenAlexFDO

Authors Taisuke Izumi

Publication date 7 August 2014

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-09620-9_12

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Distributed verification of minimum spanning trees
• Distributed verification of minimum spanning trees
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• The verified incremental design of a distributed spanning tree algorithm: Extended abstract
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• scientific article; zbMATH DE number 1786476
• Distributed algorithms for low stretch spanning trees
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Optimal lower bounds for distributed and streaming spanning forest computation

Cited in

(5)

• The lower bounds on distributed shortest paths
• Distributed verification and hardness of distributed approximation
• Distributed verification and hardness of distributed approximation
• Proving Distributed Algorithms for Mobile Agents: Examples of Spanning Tree Computation in Anonymous Networks
• The complexity landscape of distributed locally checkable problems on trees

This page was built for publication: Randomized Lower Bound for Distributed Spanning-Tree Verification

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