Characterizations of classes of graphs recognizable by local computations

DOI10.1007/S00224-003-1062-1MaRDI QIDQ1879372zbMATH OpenOpenAlexFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42) Distributed algorithms (68W15)

Recommendations

• On the recognition of families of graphs with local computations
• scientific article; zbMATH DE number 512941
• Publication:4502806
• What Can be Computed Locally?
• Local computations in graphs: the case of cellular edge local computations

Cited in

(16)

• The computational power of simple protocols for self-awareness on graphs
• Locally derivable graphs
• Local computations on triangular graphs
• scientific article; zbMATH DE number 1533813 (Why is no real title available?)
• An efficient algorithm to recognize locally equivalent graphs
• Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
• Election in partially anonymous networks with arbitrary knowledge in message passing systems
• Deducible and equivalent structural knowledges in distributed algorithms
• On the recognition of families of graphs with local computations
• Labelled (Hyper)Graphs, Negotiations and the Naming Problem
• Sublinear fully distributed partition with applications
• Workshop on Graph Computation Models
• A hierarchy of dismantlings in graphs
• scientific article; zbMATH DE number 3949732 (Why is no real title available?)
• On the power of synchronization between two adjacent processes
• scientific article; zbMATH DE number 1504828 (Why is no real title available?)

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

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