Clique-width

From Wikipedia, the free encyclopedia

In graph theory, the clique-width of a graph G is 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 ( noted i(v) )
  2. Disjoint union of two labeled graphs G and H ( denoted G \oplus H )
  3. Joining by an edge every vertex lebeled i to every vertex labeled j (denoted n(i,j))
  4. Renaming label i to label j ( denoted p(i,j) )

Cographs are exactly the graphs with clique-width at most 2; every distance-hereditary graph has clique-width at most 3 (Golumbic & Rotics 2000). Many optimization problems that are NP-hard for more general classes of graphs may be solved efficiently by dynamic programming on graphs of bounded clique-width (Cogis & Thierry 2005; Courcelle, Makowski & Rotics 2000). The theory of graphs of bounded clique-width resembles that for graphs of bounded treewidth, but unlike treewidth allows for dense graphs.

[edit] References

Languages