Function simulation, graph grammars and colourings

DOI10.1080/00207160.2012.752075zbMath1273.05063MaRDI 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 grammars; uniquely colourable graphs; reversible computation; defining sets; function evaluation; graph amalgams; sequential graph colouring

Mathematics Subject Classification ID

68R01: General topics of discrete mathematics in relation to computer science

03D15: Complexity of computation (including implicit computational complexity)

05C15: Coloring of graphs and hypergraphs

68Q42: Grammars and rewriting systems

05C85: Graph algorithms (graph-theoretic aspects)

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