More efficient algorithms for polynomial-time solvable graph problems

多项式时间可解图问题的更有效算法

• 批准号: 327762855
• 负责人: Dr. André Nichterlein, since 5/2022
• 金额: --
• 依托单位: Fachgebiet Algorithmik und Komplexitätstheorie
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2017
• 资助国家: 德国
• 起止时间: 2016-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/327762855?language=en
• 关键词: More; efficient; algorithms; polynomial; time

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.

中心项目的目标是开发新的，重要的特殊情况下加速算法的多项式时间可解图问题。多项式时间边界中的高次应通过使用参数化算法设计和分析的方法来规避（迄今为止，这些方法主要集中在NP难问题上）。特别感兴趣的是（准）线性时间算法的常数参数值，可能的参数，例如，是最大顶点度或树宽的基础图形。通过参数化，可以克服最近发现的多项式运行时间（例如，所有对最短路径）的一些下限，这是潜在可行的。除了经典的参数化研究的NP难问题，现在也多项式参数函数很容易。该项目既做基础理论研究，也做社会网络分析应用的研究。因此，该项目包括两条主要研究路线。首先，研究基本图问题（例如流和直径计算），并研究社交网络问题（还包括解决这些问题的启发式方法）。这个项目的主要兴趣的技术是参数层次结构，有效的数据减少和问题的核心化，“距离平凡”参数化，和合适的数据结构的发展。