Treffer: Classification of Distributed Binary Labeling Problems
Title:
Classification of Distributed Binary Labeling Problems
Authors:
Contributors:
Attiya, Hagit
Source:
Leibniz International Proceedings in Informatics (LIPIcs), 179 ; 34th International Symposium on Distributed Computing (DISC 2020)
Publisher Information:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Publication Year:
2020
Collection:
ETH Zürich Research Collection
Subject Terms:
Document Type:
Konferenz
conference object
File Description:
application/application/pdf
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/isbn/978-3-95977-168-9; http://hdl.handle.net/20.500.11850/466923
DOI:
10.3929/ethz-b-000466923
Rights:
info:eu-repo/semantics/openAccess ; http://creativecommons.org/licenses/by/3.0/ ; Creative Commons Attribution 3.0 Unported
Accession Number:
edsbas.E7F37AD
Database:
BASE
Weitere Informationen
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees. ; ISSN:1868-8969