Simple distributed spanners in dense congest networks

DOI10.1007/978-3-030-38919-2_22MaRDI QIDQ3297775zbMATH OpenOpenAlexFDO

Authors Leonid Barenboim, Tzalik Maimon

Publication date 20 July 2020

Published in SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-38919-2_22

zbMATH Keywords

distributed computingdiversityspanners

Mathematics Subject Classification ID

Connectivity (05C40) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Congested clique algorithms for graph spanners
• Fast Deterministic Distributed Algorithms for Sparse Spanners
• Fast deterministic distributed algorithms for sparse spanners
• On the locality of distributed sparse spanner construction
• Improved deterministic distributed construction of spanners

Cites work

• (1 + εΒ) -spanner constructions for general graphs
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• All-Pairs Almost Shortest Paths
• An Optimal Synchronizer for the Hypercube
• Computing almost shortest paths
• Deterministic distributed \((\Delta + o(\Delta))\)-edge-coloring, and vertex-coloring of graphs with bounded diversity
• Distributed Computing: A Locality-Sensitive Approach
• Distributed deterministic edge coloring using bounded neighborhood independence
• Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
• Graph spanners
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• Improved deterministic distributed construction of spanners
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• MST in \(O(1)\) rounds of congested clique
• On the locality of distributed sparse spanner construction
• Optimal deterministic routing and sorting on the congested clique
• Sublinear fully distributed partition with applications
• Toward optimal bounds in the congested clique, graph connectivity and MST

Cited in

(4)

• Distributed construction of low-interference spanners
• Congested clique algorithms for graph spanners
• Distributed Spanner Approximation
• Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election

This page was built for publication: Simple distributed spanners in dense congest networks

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