Clique-width
In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of labels needed to construct by means of the following 4 operations : Creation of a new vertex with label (denoted by ) Disjoint union of two labeled graphs and (denoted by ) Joining by an edge every vertex labeled to every vertex labeled (denoted by ), where Renaming label to label (denoted by ) Graphs of bounded clique-width include the cographs and distance-hereditary graphs. Although it is NP-hard to compute the clique-width when it is unbounded, and unknown whether it can be computed in polynomial time when it is bounded, efficient approximation algorithms for clique-width are known. Based on these algorithms and on Courcelle's theorem, many graph optimization problems that are NP-hard for arbitrary graphs can be solved or approximated quickly on the graphs of bounded clique-width. The construction sequences underlying the concept of clique-width were formulated by Courcelle, Engelfriet, and Rozenberg in 1990 and by . The name "clique-width" was used for a different concept by