论文标题
定向分支宽度：树宽的定向类似物
Directed branch-width: A directed analogue of tree-width
论文作者
论文摘要
古尔斯基（Gurski）和旺克（Wanke）表明，当且仅当其关联的有向线图类具有有限的集合宽度时，图C类具有有界的树宽。不可避免地 - 询问这种关系是否提升到定向图 - 我们引入了一种新的Digraph宽度度量：我们通过研究有针对性的线图具有界限的图形来获得它。因此，为了概括古尔斯基（Gurski）和旺克（Wanke）的上述结果，我们将分支宽度的自然泛化引入到挖掘物上，并相应地将其命名。 定向分支宽度是真正的定向宽度量，因为它不能用来绑定基本的无向树宽度的值。尽管如此，这两个度量仍然密切相关：Digraph D的定向分支宽度与仅在源和水槽处的其基础无向图的分支宽度不同。这种关系使我们能够从有界的树宽范围内的定向图扩展到一系列算法结果，到具有有界的定向分支宽度的严格较大类的挖掘物。
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 it by investigating digraphs whose directed line graphs have bounded cliquewidth. Thus, to generalize Gurski and Wanke's aforementioned result, we introduce a natural generalization of branch-width to digraphs and we name it accordingly. Directed branch-width is a genuinely directed width-measure insofar as it cannot be used to bound the value of the underlying undirected tree-width. Despite this, the two measures are still closely related: the directed branch-width of a digraph D can differ from the branch-width of its underlying undirected graph only at sources and sinks. This relationship allows us to extend a range of algorithmic results from directed graphs with bounded underlying treewidth to the strictly larger class of digraphs having bounded directed branch-width.
