Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond

DOI10.4230/LIPICS.DISC.2019.18zbMath1515.68372MaRDI QIDQ6487534

Unnamed Author, Mohsen Ghaffari

Publication date: 3 February 2023

zbMATH Keywords

maximal independent setnetwork decompositiondistributed graph algorithmsneighborhood cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (4)

Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ Distributed Spanner Approximation ⋮ Distributed Lower Bounds for Ruling Sets

This page was built for publication: Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond