Added to Favorites

Related Searches

Definitions

Nearby Words

Related Questions

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 :## References

| doi = 10.1016/j.disopt.2005.03.004}}.

- Creation of a new vertex v with label i (noted i(v) )
- Disjoint union of two labeled graphs G and H (denoted $G\; oplus\; H$ )
- Joining by an edge every vertex lebeled i to every vertex labeled j (denoted n(i,j))
- 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 . 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 (). The theory of graphs of bounded clique-width resembles that for graphs of bounded treewidth, but unlike treewidth allows for dense graphs.

- .
- .
| doi = 10.1142/S0129054100000260}}.

- .

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday May 08, 2008 at 08:46:39 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday May 08, 2008 at 08:46:39 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.