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

DOI10.1016/S1571-0661(05)80197-5zbMATH Open1114.68455OpenAlexW2089668714MaRDI QIDQ4222809FDOQ4222809

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

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

Mathematics Subject Classification ID

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

Cites Work

• Coverings and minors: Application to local computations in graphs
• Locality in Distributed Graph Algorithms
• Title not available (Why is that?)
• What can be computed locally?
• Title not available (Why is that?)
• Computing with graph rewriting systems with priorities
• Different local controls for graph relabeling systems

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)