Function simulation, graph grammars and colourings

References

• D. Achlioptas and A. Coja-Oghlan, Algorithmic barriers from phase transitions, Proceedings of Annual IEEE Symposium on Foundations of Computer Science, FOCS, Philadelphia, PA, 2008, pp. 793–802.
   Google Scholar
• Arora , S. and Barak , B. 2009 . Computational Complexity: A Modern Approach , Cambridge : Cambridge University Press .
   Google Scholar
• Baader , F. and Nipkow , T. 1999 . Term Rewriting and All That , Cambridge : Cambridge University Press .
   Google Scholar
• S.R. Blackburn, Combinatorics and threshold cryptography, in Combinatorial Designs and Their Applications (Milton Keynes, 1997), F.C. Holroyd, K.A.S. Quinn, C. Rowley, B.S. Web, eds., Research Notes in Mathematics, Vol. 403, Chapman & Hall/CRC, Boca Raton, FL, 1999, pp. 49–70.
   Google Scholar
• Chaudhry , G. R. , Ghodosi , H. and Seberry , J. 1998 . Perfect secret sharing schemes from room squares . J. Combin. Math. Combin. Comput. , 28 : 55 – 61 .
   Google Scholar
• Cooper , J. , Donovan , D. and Seberry , J. 1994 . Secret sharing schemes arising from Latin squares . Bull. Inst. Combin. Appl. , 12 : 33 – 43 .
   Google Scholar
• Daneshgar , A. 2001 . Forcing structures and cliques in uniquely vertex colourable graphs . SIAM J. Discrete Math. , 14 : 433 – 445 . (doi:10.1137/S0895480196304994)
   Web of Science ®Google Scholar
• A. Daneshgar and R. Ebrahimi Soorchaei, On sequential colouring of graphs and its defining sets (29 December 2008). Available at arXiv:0812.4920.
   Google Scholar
• A. Daneshgar, A. Rahimi, and S. Taati, Graph coloring and function simulation (18 August 2010). Available at arXiv:1008.3015v1.
   Google Scholar
• Daneshgar , A. , Hajiabolhassan , H. and Taati , S. 2010 . On the complexity of unique list colourability and the fixing number of graphs . Ars Combin. , 97 : 301 – 319 .
   Web of Science ®Google Scholar
• Drewes , F. , Kreowski , H.-J. and Habel , A. 1997 . “ Hyperedge replacement graph grammars ” . In Handbook of Graph Grammars and Computing by Graph Transformation , Edited by: Rozenberg , G. Vol. I , 95 – 162 . River Edge , NJ : World Scientific Publishing .
   Google Scholar
• Ehrig , H. , Engels , G. , Kreowski , H. J. and Rozenberg , G. 1999 . Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 2 Applications, Languages and Tools , Edited by: Ehrig , H. , Engels , G. , Kreowski , H. J. and Rozenberg , G. River Edge , NJ : World Scientific Publishing Co. Inc .
   Google Scholar
• Ehrig , H. , Kreowski , H. J. , Montanari , U. and Rozenberg , G. 1999 . Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 2 Concurrency, Parallelism, and Distribution , Edited by: Ehrig , H. , Kreowski , H. J. , Montanari , U. and Rozenberg , G. River Edge , NJ : World Scientific Publishing Co. Inc .
   Google Scholar
• Ehrig , H. , Ehrig , K. , Prange , U. and Taentzer , G. 2006 . Fundamentals of Algebraic Graph Transformation , Berlin : Springer-Verlag . Monographs in Theoretical Computer Science, An EATCS Series
   Google Scholar
• Emden-Weinert , T. , Hougardy , S. and Kreuter , B. 1998 . Uniquely colourable graphs and the hardness of colouring graphs of large girth . Combin. Probab. Comput. , 7 : 375 – 386 . (doi:10.1017/S0963548398003678)
   Web of Science ®Google Scholar
• F. Eugeni, Combinatorics and cryptography, Combinatorics ’90 (Gaeta, 1990), Ann. Discrete Math., Vol. 52, North-Holland, Amsterdam, 1992, pp. 159–174.
   Google Scholar
• Feng , K. , Niederreiter , H. and Xing , C. 2004 . Coding, Cryptography and Combinatorics , Edited by: Feng , K. , Niederreiter , H. and Xing , C. Basel : Birkhäuser Verlag . Progress in Computer Science and Applied Logic Vol. 23
   Google Scholar
• Fitina , L. F. and Lal , S. P. 2006 . Access schemes based on perfect critical set partitions and transformations . Australas. J. Combin. , 34 : 229 – 237 .
   Google Scholar
• Gonzalez , T. F. 2007 . Handbook of Approximation Algorithms and Metaheuristics , Edited by: Gonzalez , T. F. Boca Raton , FL : Chapman & Hall/CRC . Chapman & Hall/CRC Computer and Information Science Series
   Google Scholar
• Guruswami , V. , Håstad , J. and Sudan , M. 2002 . Hardness of approximate hypergraph colouring . SIAM J. Comput. , 31 ( 6 ) : 1663 – 1686 . (doi:10.1137/S0097539700377165)
   Web of Science ®Google Scholar
• Hell , P. and Nešetřil , J. 2004 . Graphs and Homomorphisms , Oxford : Oxford University Press . Oxford Lecture Series in Mathematics and Its Applications Vol. 28
   Google Scholar
• Jensen , T. R. and Toft , B. 1995 . Graph Coloring Problems , New York : John Wiley & Sons Inc . Wiley-Interscience Series in Discrete Mathematics and Optimization Vol. 28
   Google Scholar
• Krzakała , F. and Zdeborová , L. 2008 . Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems . J. Phys. Conf. Ser. , 95 Article no. 012012., (doi:10.1088/1742-6596/95/1/012012)
   Google Scholar
• Krzakała , F. and Zdeborová , L. 2009 . Hiding quiet solutions in random constraint satisfaction problems . Phys. Rev. Lett. , 102 Article no. 238701, (doi:10.1103/PhysRevLett.102.238701)
   PubMed Web of Science ®Google Scholar
• Kulesza , K. and Kotulski , Z. 2005 . Addressing New Challenges by Building Security Protocols Around Graphs , 301 – 306 . Berlin : Springer . Security Protocols, Lecture Notes in Computer Science Vol. 3364
   Google Scholar
• van Lint , J. H. and Wilson , R. M. 2001 . A Course in Combinatorics , 2 , Cambridge : Cambridge University Press .
   Google Scholar
• Martin , K. M. 2007 . The Combinatorics of Cryptographic Key Establishment , 223 – 273 . Cambridge : Cambridge University Press . Surveys in Combinatorics, London Mathematical Society Lecture Note Series Vol. 346
   Google Scholar
• Nešetřil , J. 1979 . Amalgamation of graphs and its applications, Second International Conference on Combinatorial Mathematics (New York, 1978) . Ann. New York Acad. Sci. , 319 : 415 – 428 . (doi:10.1111/j.1749-6632.1979.tb32819.x)
   Google Scholar
• Nielsen , M. A. and Chuang , I. L. 2000 . Quantum Computation and Quantum Information , Cambridge : Cambridge University Press .
   Google Scholar
• Radhakrishnan , J. and Sudan , M. 2007 . On Dinur's proof of the PCP theorem . Bull. Amer. Math. Soc. (N.S.) , 44 : 19 – 61 . (doi:10.1090/S0273-0979-06-01143-8)
   Web of Science ®Google Scholar
• Rozenberg , G. 1997 . Handbook of Graph Grammars and Computing by Graph Transformation , Edited by: Rozenberg , G. Vol. 1 , River Edge , NJ : Foundations, World Scientific Publishing Co. Inc .
   Google Scholar
• H.J. Schneider, Graph Transformations, an Introduction to the Categorical Approach, 2010. Available at https://www2.informatik.uni-erlangen.de/staff/schneider/gtbook/index.html.
   Google Scholar
• Semerjian , G. 2008 . On the freezing of variables in random constraint satisfaction problems . J. Statist. Phys. , 130 : 251 – 293 . (doi:10.1007/s10955-007-9417-7)
   Web of Science ®Google Scholar
• Stallings , J. R. 1983 . Topology of finite graphs . Inventions Mathematicae , 71 : 551 – 565 . (doi:10.1007/BF02095993)
   Web of Science ®Google Scholar
• A. Tsiatas, Phase transitions in Boolean satisfiability and graph coloring, 2008. Available at http://cseweb.ucsd.edu/ atsiatas/cs.html.
   Google Scholar
• Valiant , L. G. and Vazirani , V. V. 1986 . NP is as easy as detecting unique solutions . Theoret. Comput. Sci. , 47 : 85 – 93 . (doi:10.1016/0304-3975(86)90135-0)
   Web of Science ®Google Scholar
• West , D. B. 1996 . Introduction to Graph Theory , Upper Saddle River , NJ : Prentice Hall Inc .
   Google Scholar
• Zdeborová , L. and Krzakała , F. 2007 . Phase transitions in the coloring of random graphs . Phys. Rev. E Statist. Nonlinear Soft Matter Phys. , 76 ( 3 ) Article no. 031131.
   Web of Science ®Google Scholar