Graph operations characterizing rank-width

摘要: Graph complexity measures such as tree-width, clique-width and rank-width are important because they yield Fixed Parameter Tractable algorithms. These algorithms based on hierarchical decompositions of the considered graphs, boundedness conditions graph operations that, more or less explicitly, recombine components into larger graphs. Rank-width is defined in a combinatorial way, tree, not terms operations. We define graphs that characterize help for construction algorithms, especially problems specified monadic second-order logic.