Characterizations of classes of graphs recognizable by local computations

DOI10.1007/S00224-003-1062-1zbMATH Open1069.68561OpenAlexW2037262262MaRDI QIDQ1879372FDOQ1879372

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

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

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)

Cited In (16)

• The computational power of simple protocols for self-awareness on graphs
• Locally derivable graphs
• Title not available (Why is that?)
• Local computations on triangular graphs
• 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
• Title not available (Why is that?)
• On the power of synchronization between two adjacent processes
• Title not available (Why is that?)

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)