Polynomial graph transformability

DOI10.1016/J.TCS.2011.12.039MaRDI QIDQ418788zbMATH OpenOpenAlexFDO

Authors Sabine Kuske, Hans-Jörg Kreowski

Publication date 30 May 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.12.039

zbMATH Keywords

NP-completenessreductiongraph transformationsatisfiability problempolynomial graph transformation unit

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph theory (including graph drawing) in computer science (68R10) Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1437942 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• Applications of graph transformations with industrial relevance. Third international symposium, AGTIVE 2007, Kassel, Germany, October 10--12, 2007. Revised selected and invited papers
• Graph Transformation Units – An Overview
• Graph transformation. 1st international conference, ICGT 2002, Barcelona, Spain, October 7--12, 2002. Proceedings
• Graph transformations. 4th international conference, ICGT 2008, Leicester, United Kingdom, September 7--13, 2008. Proceedings
• Graph transformations. 5th international conference, ICGT 2010, Enschede, The Netherlands, September 27 -- October 2, 2010. Proceedings
• Graph transformations. Second international conference, ICGT 2004, Rome, Italy, September 28 -- October 2, 2004. Proceedings.
• Graph transformations. Third international conference, ICGT 2006, Natal, Rio Grande do Norte, Brazil, September 17--23, 2006. Proceedings
• Handbook of Graph Grammars and Computing by Graph Transformation
• Handbook of Graph Grammars and Computing by Graph Transformation
• On Moore Graphs with Diameters 2 and 3
• SAT-Based Scalable Formal Verification Solutions

Cited in

(2)

• Adjacency polynomials of digraph transformations
• A graph-transformational approach for proving the correctness of reductions between NP-problems

This page was built for publication: Polynomial graph transformability

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