Whether the clique-width of graphs in a certain class of graphs is bounded or not, is an
important question from an algorithmic point of view, as many problems that are NP-hard in …

The study of graph structure has advanced in recent years with great strides: finite graphs
can be described algebraically, enabling them to be constructed out of more basic elements …

We construct a polynomial-time algorithm to approximate the branch-width of certain
symmetric submodular functions, and give two applications. The first is to graph “clique …

The rank-width is a graph parameter related in terms of fixed functions to clique-width but
more tractable. Clique-width has nice algorithmic properties, but no good “minor” relation is …

We show that determining if an $ n $-vertex graph has twin-width at most 4 is NP-complete,
and requires time $2^{\Omega (n/\log n)} $ unless the Exponential-Time Hypothesis fails …

The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the
truth value of a first order sentence in a generalized product of first order structures by …

We discuss the parametrized complexity of counting and evaluation problems on graphs
where the range of counting is definable in monadic second-order logic (MSOL). We show …

Treewidth is generally regarded as one of the most useful parameterizations of a graph's
construction. Clique-width is a similar parameterization that shares one of the powerful …

Besides the very successful concept of tree-width (see [Bodlaender, H. and Koster, A.(2007)
Combinatorial optimisation on graphs of bounded treewidth. These are special issues on …

In this survey, we review practical algorithms for graph-theoretic problems that are
expressible in monadic second-order logic. Monadic second-order (MSO) logic allows …