Characterizations of classes of graphs recognizable by local computations

DOI10.1007/s00224-003-1062-1zbMath1069.68561OpenAlexW2037262262MaRDI QIDQ1879372

Emmanuel Godard, Anca Muscholl, Yves Métivier

Publication date: 22 September 2004

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-003-1062-1

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (8)

The computational power of simple protocols for self-awareness on graphs ⋮ A hierarchy of dismantlings in graphs ⋮ Election in partially anonymous networks with arbitrary knowledge in message passing systems ⋮ Sublinear fully distributed partition with applications ⋮ Labelled (Hyper)Graphs, Negotiations and the Naming Problem ⋮ Workshop on Graph Computation Models ⋮ On the power of synchronization between two adjacent processes ⋮ Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds

This page was built for publication: Characterizations of classes of graphs recognizable by local computations