Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
We study the awake complexity of graph problems that belong to the class O-LOCAL, which includes a subset of problems solvable by sequential greedy algorithms, such as (Δ + 1)-coloring and maximal independent set. It is known from previous work that, in n-node graphs of maximum degree Δ, any problem in the class O-LOCAL can be solved by a deterministic distributed algorithm with awake complexity O (log Δ + log* n).
Authors
- Alkida Balliu (ORCID: https://orcid.org/0000-0001-5293-8365)
- Mikaël Rabie (ORCID: https://orcid.org/0000-0001-6782-7625)
- Dennis Olivetti (ORCID: https://orcid.org/0000-0002-6600-6443)
- Pierre Fraigniaud (ORCID: https://orcid.org/0000-0003-4534-4803)
Institutions
- Centre National de la Recherche Scientifique (FR)
- Université Paris Cité (FR)
- Sorbonne Paris Cité (FR)
- Gran Sasso Science Institute (IT)
Publication Details
- Published
- 2025-06-13
- DOI
- https://doi.org/10.1145/3732772.3733499
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Agence Nationale de la Recherche
- Ministero dell’Istruzione, dell’Università e della Ricerca