Upper bounds to the clique width of graphs
作者： Bruno Courcelle , Stephan Olariu
DOI: 10.1016/S0166-218X(99)00184-5
关键词:
摘要: … is called clique width. In this paper we bound the clique width of a graph in terms of its tree width on the one hand, and of the clique width of its edge complement on the other. …
elsevier.com
sci-hub.se 参考文章(25)
J. Engelfriet, G. Rozenberg, Node replacement graph grammars Handbook of graph grammars and computing by graph transformation. pp. 1- 94 ,(1997)
T. Harju, G. Rozenberg, A. Ehrenfeucht, 2-structures—a framework for decomposition and transformation of graphs Handbook of graph grammars and computing by graph transformation. pp. 401- 478 ,(1997)
B. Courcelle, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues Theoretical Informatics and Applications. ,vol. 26, pp. 257- 286 ,(1992) , 10.1051/ITA/1992260302571
Joost Engelfriet, A Characterization of Context-Free NCE Graph Languages by Monadic Second-Order Logic on Trees international workshop on graph grammars and their application to computer science. pp. 311- 327 ,(1990) , 10.1007/BFB0017397
B. Courcelle, The expression of graph properties and graph transformations in monadic second-order logic Handbook of graph grammars and computing by graph transformation. pp. 313- 400 ,(1997)
Alain Cournier, Michel Habib, A New Linear Algorithm for Modular Decomposition colloquium on trees in algebra and programming. pp. 68- 84 ,(1994) , 10.1007/BFB0017474
Bruno Courcelle, The monadic second-order logic of graphs VIII: Orientations Annals of Pure and Applied Logic. ,vol. 72, pp. 103- 143 ,(1995) , 10.1016/0168-0072(95)94698-V
B. Courcelle, An axiomatic definition of context-free rewriting and its application to NLC graph grammars Theoretical Computer Science. ,vol. 55, pp. 141- 181 ,(1987) , 10.1016/0304-3975(87)90102-2
Bruno Courcelle, Joost Engelfriet, Grzegorz Rozenberg, Handle-rewriting hypergraph grammars Journal of Computer and System Sciences. ,vol. 46, pp. 218- 270 ,(1993) , 10.1016/0022-0000(93)90004-G
B. Courcelle, M. Mosbah, Monadic second-order evaluations on tree-decomposable graphs Theoretical Computer Science. ,vol. 109, pp. 49- 82 ,(1993) , 10.1016/0304-3975(93)90064-Z