☆ 4.3 Article

Distributed half-integral matching and beyond

THEORETICAL COMPUTER SCIENCE (2024)

Related references

Note: Only part of the references are listed.

Article Computer Science, Hardware & Architecture

Lower Bounds for Maximal Matchings and Maximal Independent Sets

Alkida Balliu et al.

Summary: Research shows that algorithms for finding maximal matchings or maximal independent sets in distributed computing depend on the number of nodes n and the maximum degree Δ, with a significant gap between upper and lower bounds. While the dependency on n has been optimized, the dependency on Δ remains a mystery.

JOURNAL OF THE ACM (2021)

Add to Collection

Article Computer Science, Theory & Methods