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
graph grammars; uniquely colourable graphs; reversible computation; defining sets; function evaluation; graph amalgams; sequential graph colouring
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
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