In the last decades, considerable efforts have been spent to characterize what makes NP-hard problems tractable. A successful approach in this line of research is the theory of parameterized complexity introduced by Downey and Fellows in the nineties. In this framework, the complexity of a problem is not measured only in terms of the input size, but also in terms of a parameter on the input. One of the most well-studied parameters is tree-width, a graph parameter which measures how close a graph is to the topological structure of a tree. It appears that tree-width has numerous structural properties and algorithmic applications.
However, only sparse graph classes can have bounded tree-width. But, many NP-hard problems are tractable on dense graph classes. Most of the time, this tractability can be explained by the ability of these graphs to be recursively decomposable along vertex bipartitions $(A,B)$ where the adjacency between $A$ and $B$ is simple to describe. A lot of graph parameters -- called width measures -- have been defined to characterize this ability, the most remarkable ones are certainly clique-width, rank-width, and mim-width. In this thesis, we study the algorithmic properties of these width measures.
We provide a framework that generalizes and simplifies the tools developed for tree-width and for problems with a constraint of acyclicity or connectivity such as Connected Vertex Cover, Connected Dominating Set, Feedback Vertex Set, etc. For all these problems, we obtain $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ time algorithms parameterized respectively by clique-width, $\mathbb{Q}$-rank-width, rank-width and mim-width. We also prove that there exists an algorithm solving Hamiltonian Cycle in time $n^{O(k)}$, when a clique-width decomposition of width $k$ is given. Finally, we prove that we can count in polynomial time the minimal transversals of $\beta$-acyclic hypergraphs and the minimal dominating sets of strongly chordal graphs. All these results offer promising perspectives towards a generalization of width measures and their algorithmic applications.