|
In graph theory, the clique-width of a graph is the minimum number of labels needed to construct by means of the following 4 operations : #Creation of a new vertex ''v'' with label ''i'' ( noted ''i(v)'' ) #Disjoint union of two labeled graphs ''G'' and ''H'' ( denoted ) #Joining by an edge every vertex labeled ''i'' to every vertex labeled ''j'' (denoted ''n(i,j)''), where #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. In particular, every graph property that can be expressed in MSO1 monadic second-order logic (a form of logic allowing quantification over sets of vertices) has a linear-time algorithm for graphs of bounded clique-width, by a form of Courcelle's theorem. The theory of graphs of bounded clique-width resembles that for graphs of bounded treewidth, but unlike treewidth allows for dense graphs. If a family of graphs has bounded clique-width, then either it has bounded treewidth or every complete bipartite graph is a subgraph of a graph in the family. Treewidth and clique-width are also connected through the theory of line graphs: a family of graphs has bounded treewidth if and only if their line graphs have bounded clique-width. == See also == * Branch-width * Rank-width 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Clique-width」の詳細全文を読む スポンサード リンク
|