Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10151236 | Discrete Applied Mathematics | 2018 | 20 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bruno Courcelle,