Function simulation, graph grammars and colourings

DOI10.1080/00207160.2012.752075zbMath1273.05063OpenAlexW1983838078MaRDI QIDQ2855758

Alireza Rahimi, Siamak Taati, Amir Daneshgar

Publication date: 22 October 2013

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160.2012.752075

zbMATH Keywords

graph grammarsuniquely colourable graphsreversible computationdefining setsfunction evaluationgraph amalgamssequential graph colouring

Mathematics Subject Classification ID

General topics of discrete mathematics in relation to computer science (68R01) Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15) Grammars and rewriting systems (68Q42) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On cylindrical graph construction and its applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Topology of finite graphs
• NP is as easy as detecting unique solutions
• On the freezing of variables in random constraint satisfaction problems
• Fundamentals of algebraic graph transformation
• Forcing Structures and Cliques in Uniquely Vertex Colorable Graphs
• Hardness of Approximate Hypergraph Coloring
• Handbook of Approximation Algorithms and Metaheuristics
• On Dinur’s proof of the PCP theorem
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Handbook of Graph Grammars and Computing by Graph Transformation
• Term Rewriting and All That
• Computational Complexity