More efficient algorithms for polynomial-time solvable graph problems

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

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.