Brief Announcement: Classification of Distributed Binary Labeling Problems

DOI10.1145/3382734.3405703MaRDI QIDQ5855255zbMATH OpenOpenAlexWikidataFDO

Authors Alkida Balliu, Sebastian F. Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela

Publication date 15 March 2021

Published in Proceedings of the 39th Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.13294, https://aaltodoc.aalto.fi/handle/123456789/111066

zbMATH Keywords

graph problemsLOCAL modeldistributed computational complexitylocally checkable labeling problems

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• Classification of distributed binary labeling problems
• Graph labelings derived from models in distributed computing: A complete complexity classification
• New classes of distributed time complexity
• Almost global problems in the LOCAL model
• Almost global problems in the LOCAL model

Cited in

(11)

• Linial for lists
• The complexity landscape of distributed locally checkable problems on trees
• Distributed algorithms for fractional coloring
• Distributed Data Structures: A Survey on Informative Labeling Schemes
• Factor-of-iid balanced orientation of non-amenable graphs
• Classification of distributed binary labeling problems
• Distributed graph problems through an automata-theoretic Lens
• Exponential speedup over locality in \textsf{MPC} with optimal memory
• Distributed Lower Bounds for Ruling Sets
• Distributed graph problems through an automata-theoretic lens
• Local conflict coloring revisited: Linial for lists

This page was built for publication: Brief Announcement: Classification of Distributed Binary Labeling Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5855255)