Distributed MIS in O (log log n) Awake Complexity

Dufoulon, F; Moses, WK ; Pandurangan, G

Dufoulon, F (通讯作者),Univ Houston, Houston, TX 77004 USA.

PROCEEDINGS OF THE 2023 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, PODC 2023, 2023; (): 135

Abstract

Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of int......

Full Text Link