Directed branch-width: A directed analogue of tree-width.

摘要: We introduce a new digraph width measure called directed branch-width. To do this, we generalize characterization of graph classes bounded tree-width in terms their line graphs to digraphs. Under parameterizations by branch-width obtain linear time algorithms for many problems, such as Hamilton path and Max-Cut, which are hard when parameterized other known measures. More generally, an algorithmic meta-theorem the model-checking problem restricted variant MSO_2-logic on