Analysis of Graph Parameters for Directed Graphs

在这个方案中，我们考虑有向图的图参数。我们对团宽度、NLC-宽度和RAKWIDTH的有向版本以及树宽度的有向版本的几种方法感兴趣。我们希望在图论领域以及在特殊图的算法方面取得成果。我们的项目有以下主要目标。(1.)应分析特殊图形类的宽度。我们对上界和下界感兴趣。(2)所有宽度不超过k的有向图的结构应该刻画几个参数。(3)我们希望寻找如何找到参数的底层树形结构的方法。(4)限制在有限宽度有向图上的硬有向图问题的可解性应该得到探索。(5)通过运行时间的实验研究，从实用的角度来验证我们的算法是否有用。

In this proposal we consider graph parameters for directed graphs. We are interested in directed versions of clique-width, NLC-width, and rankwidth as well as several approaches for a directed version of tree-width. We want to obtain results in the field of graph theory as well as in algorithmic of special graphs.Our project has the following main aims. (1.) The width of special graph classes should be analyzed. We are interested in upper and in lower bounds. (2.) The structure of all directed graphs of width at most k should be characterized for several parameters. (3.) We want to look for methods how we can find the underlying tree-structure of the parameters. (4.) The solvability of hard digraph problems restricted to digraphs of bounded width should be explored. (5.) By experimental studys of running times it should be verified whether our algorithms are useful from a practical point of view.