scientific article; zbMATH DE number 512941

MaRDI QIDQ4281656zbMATH OpenFDO

Authors Igor Litovsky, Wiesław Zielonka, Yves Métivier

Publication date 7 April 1994

zbMATH Keywords

graph recognitionlocal computations on graphsplanar graphsrewriting systems over labelled graphsseries parallel graphssimulation of finite automata on words

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Grammars and rewriting systems (68Q42) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the recognition of families of graphs with local computations
• Characterizations of classes of graphs recognizable by local computations
• Publication:4502806
• scientific article; zbMATH DE number 1923048
• Definitions and comparisons of local computations on graphs (extended abstract)

Cited in

(21)

• Generating irregular partitionable data structures
• Characterizations of classes of graphs recognizable by local computations
• Distributed enumeration
• Local computations on triangular graphs
• Local computations in graphs: the case of cellular edge local computations
• The computational power of simple protocols for self-awareness on graphs
• Checking Global Graph Properties by Means of Local Computations: the Majority Problem
• Different local controls for graph relabeling systems
• scientific article; zbMATH DE number 1504828 (Why is no real title available?)
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• scientific article; zbMATH DE number 1923048 (Why is no real title available?)
• Locally computable enumerations
• On the Complexity of Local Graph Transformations
• Definitions and comparisons of local computations on graphs (extended abstract)
• Foundations of Software Science and Computation Structures
• Limits of local algorithms over sparse random graphs
• Node and edge averaged complexities of local graph problems
• Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
• Computational complexity of covering coloured mixed multigraphs with simple degree partitions
• Computational complexity of covering multigraphs with semi-edges: small cases
• Computational complexity of covering regular trees

This page was built for publication:

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