Analysis of Graph Parameters for Directed Graphs

点击翻译按钮获取中文摘要

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.