Lower Bounds for Maximal Matchings and Maximal Independent Sets

DOI10.1145/3461458zbMath1499.68248arXiv1901.02441OpenAlexW2908664940MaRDI QIDQ5056427

Juho Hirvonen, Jukka Suomela, Alkida Balliu, Sebastian F. Brandt, Mikaël Rabie, Dennis Olivetti

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1901.02441

zbMATH Keywords

lower boundsmaximal matchingmaximal independent setdistributed graph algorithms

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Related Items (8)

Locally checkable problems in rooted trees ⋮ Distributed half-integral matching and beyond ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Distributed half-integral matching and beyond ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Distributed MIS with Low Energy and Time Complexities ⋮ Distributed Self-Stabilizing MIS with Few States and Weak Communication ⋮ Linial for lists

This page was built for publication: Lower Bounds for Maximal Matchings and Maximal Independent Sets