文档介绍：Discrete Applied Mathematics 160 (2012) 834–865
Contents lists available at SciVerse ScienceDirect
Discrete Applied Mathematics
journal homepage:
Polynomial-time recognition of clique-width ≤ 3 graphs✩
Derek G. Corneil a, Michel Habib b, Jean-Marc Lanlignel c, Bruce Reed d, Udi Rotics e,∗
a Department of Computer Science, University of Toronto, Toronto, Ontario, Canada
b LIAFA, UMR 7089 CNRS & Université Paris Diderot - Paris 7. UFR d’Informatique - case 7014, F-75205 Paris Cedex 13, France
c LIRMM, UMR CNRS-Université Montpellier II, 161 rue Ada, 34392 Montpellier cedex 5, France
d Canada Research Chair in the Combinatorics of Complex Networks, School of Computer Science, McGill University, Montreal, Quebec, Canada
e School of Mathematics and Computer Science, Netanya Academic College, . Box 120, 42100 Netanya, Israel
a r t i c l e i n f o a b s t r a c t
Article history: Clique-width is a relatively new parameterization of graphs, philosophically similar to
Received 30 April 2010 treewidth. Clique-width is more encompassing in the sense that a graph of bounded
Received in revised form 10 February 2011 treewidth is also of bounded clique-width (but not the converse). For graphs of bounded
Accepted 15 March 2011 clique-width, given the clique-width decomposition, every optimization, enumeration or
Available online 8 May 2011
evaluation problem that can be defined by a monadic second-order logic formula using
quantifiers on vertices, but not on edges, can be solved in polynomial time.
Keywords: