William Pettersson

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

Gurski and Wanke showed that a graph class C has bounded tree-width if and only if its associated class of directed line graphs has bounded clique-width. Inevitably -- asking whether this relationship lifts to directed graphs -- we introduce a new digraph width measure: we obtain...