Clique-width
In graph theory, the clique-width of a graph G is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs.It is defined as the minimum number of labels needed to construct G by means of the following 4 operations : 1. * Creation of a new vertex v with label i (denoted by i(v)) 2. * Disjoint union of two labeled graphs G and H (denoted by ) 3. * Joining by an edge every vertex labeled i to every vertex labeled j (denoted by η(i,j)), where i ≠ j 4. * Renaming label i to label j (denoted by ρ(i,j)) 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 . By 1993, the term already had its present meaning. (Wikipedia).
