More efficient algorithms for polynomial-time solvable graph problems

该项目的中心目标是为重要的特殊情况开发多项式时间可解图问题的新的加速算法。通过使用参数化算法设计和分析的方法(目前主要集中在NP-Hard问题)，可以避免多项式时间界限中的高度限制。特别感兴趣的是用于恒定参数值的(准)线性时间算法；可能的参数例如是基础图的最大顶点度或树宽。通过参数化可以克服最近发现的多项式运行时间的一些下界(例如，对于所有对最短路径)，这是潜在的可行的。除了经典的NP-Hard问题的参数化研究外，现在还可以很容易地使用多项式参数函数。该项目既在做基础理论研究，也在进行社交网络分析中的应用研究。因此，该项目由两条主要研究路线组成。首先，研究了基本的图问题(如流量和直径计算)和社会网络问题(也包括解决这些问题的启发式方法)。该项目的主要兴趣技术是参数层次结构、有效的数据约简和问题核化、“远离琐碎”的参数化以及合适的数据结构的开发。

The central project goal is to develop new, for important special cases accelerated algorithms for polynomial-time solvable graph problems. High-degrees in the polynomial time bounds shall be circumvented by using methods of parameterized algorithm design and Analysis (which so far focusses on NP-hard problems). Of particular interest are (quasi-)linear-time algorithms for constant parameter values; possible parameters e.g. are the maximum vertex degree or the treewidth of the underlying graph. It is potentially feasible that through parameterization some of the recently discovered lower bounds for polynomial running times (e.g. for ALL PAIRS SHORTEST PATHS) can be overcome. Other than for classical parameterized studies for NP-hard Problems now also polynomial parameter functions are easily possible. The project is both doing basic theoretical research as well as research motivated by applications in social network analysis. Hence, the project consists of two main research lines. First, there is research on fundamental graph problems (such as flow and diameter computations) and there is research on social Network problems (also including heuristic approaches to solve these). The techniques of main interest for this project are parameter hierarchies, efficient data reduction and problem kernelization, "distance from triviality"-parameterizations, and the development of suitable data structures.