Locally Checkable Problems in Rooted Trees
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Терещенко Александр Владимирович · 2021
Consider any locally checkable labeling problem Π in rooted regular trees: there is a finite set of labels Σ, and for each label χ x Σ we specify what are permitted label combinations of the children for an internal node of label x (the leaf nodes are unconstrained). This formalism is expressive enough to capture many classic problems studied in distributed computing, including vertex coloring, edge coloring, and maximal independent set.