Paper Info
Title
From tree-decompositions to clique-width terms.
Abstract
Tree-width and clique-width are two important graph complexity measures that serve as parameters in many fixed-parameter tractable algorithms. We give two algorithms that transform tree-decompositions represented by normal trees into clique-width terms (a rooted tree is normal for a graph if its nodes are the vertices of the graph and every two adjacent vertices are on a path of the tree starting at the root). As a consequence, we obtain that, for certain classes of sparse graphs, clique-width is polynomially bounded in terms of tree-width. It is even linearly bounded for planar graphs and incidence graphs. These results are useful in the construction of model-checking algorithms for problems described by monadic second-order formulae, including those allowing edge set quantifications.
Year
DOI
Venue
2018
10.1016/j.dam.2017.04.040
Discrete Applied Mathematics
Keywords
Field
DocType
Tree-width,Clique-width,Sparse graph,Planar graph,Incidence graph,Fixed-parameter tractable algorithm
Block graph,Discrete mathematics,Combinatorics,Trémaux tree,Tree-depth,Chordal graph,Independent set,Treewidth,Pathwidth,Mathematics,Split graph
Journal
Volume
ISSN
Citations 
248
0166-218X
2
PageRank 
References 
Authors
0.35
16
1
Name
Order
Citations
PageRank
Bruno Courcelle13418388.00