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)

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

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)