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)

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