Checking Global Graph Properties by Means of Local Computations: the Majority Problem

DOI10.1016/S1571-0661(05)80197-5MaRDI QIDQ4222809zbMATH OpenOpenAlexFDO

Authors Igor Litovsky, Éric Sopena, Yves Métivier

Publication date 13 December 1998

Published in Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1571-0661(05)80197-5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• What Can be Computed Locally?
• Local computations in graphs: the case of cellular edge local computations
• Randomized Algorithms for Determining the Majority on Graphs
• Determining majority in networks with local interactions and very small local memory

Cites work

• scientific article; zbMATH DE number 512941 (Why is no real title available?)
• scientific article; zbMATH DE number 219259 (Why is no real title available?)
• Computing with graph rewriting systems with priorities
• Coverings and minors: Application to local computations in graphs
• Different local controls for graph relabeling systems
• Locality in Distributed Graph Algorithms
• What can be computed locally?

This page was built for publication: Checking Global Graph Properties by Means of Local Computations: the Majority Problem

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