Characterizations and Directed Path-Width of Sequence Digraphs

Frank Gurski, Carolin Rehs, Jochen Rethmann

Computing the directed path-width of a directed graph is an NP-hard problem. Even for digraphs of maximum semi-degree 3 the problem remains hard. We propose a decomposition of an i…