41 citations · 71 across the 13 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018
Comparing Linear Width Parameters for Directed Graphs
Frank Gurski, Carolin Rehs
In this paper we introduce the linear clique-width, linear NLC-width, neighbourhood-width, and linear rank-width for directed graphs. We compare these parameters with each other as…
cs.DS2018
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…
cs.DS2018★ 4 cited
Computing directed path-width and directed tree-width of recursively defined digraphs
Frank Gurski, Carolin Rehs
In this paper we consider the directed path-width and directed tree-width of recursively defined digraphs. As an important combinatorial tool, we show how the directed path-width a…