Theoretical and Practical Aspects of Kernelization

核化的理论和实践方面

• 批准号: 206471640
• 负责人: Professor Dr. Peter Rossmanith
• 金额: --
• 依托单位: Informatik 1 - Lehrgebiet Theoretische Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2012
• 资助国家: 德国
• 起止时间: 2011-12-31 至 2013-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/206471640?language=en
• 关键词: Theoretical; Practical; Aspects; Kernelization

Kernelization is an area of parameterized complexity that dealswith the study of preprocessing algorithms. A kernelizationalgorithm essentially strips away the easy parts of aproblem instance exposing the core or the kernel. This is an area thathas attracted the attention of both theoreticians and practitionersfor the interesting mathematical problems it poses and the practicalutility of many of the solutions.The objective of this project is to study both theoreticaland practical aspects of kernelization algorithms. On thetheoretical side, we plan to investigate topics suchas kernelization using non-standard parameters where somestructural aspect of the input (other than the solution size)is used as parameter. Other topics includestrong polynomial kernels, Turing kernels, and theconnection between kernelization and approximability. On thepractical side, we plan to design kernelization algorithmsfor concrete problems with the aim of implementing thesealgorithms. In particular, we want to investigate the possibility ofimproving kernels for several problems on planar graphs (among others).

核化是研究预处理算法的参数化复杂性领域。内核化算法本质上是剥离了问题实例中容易暴露核心或内核的部分。这是一个领域thathas吸引了理论家和propositionersfor有趣的数学问题，它提出了许多解决方案的实际utility.The本项目的目标是研究核算法的理论和实践方面。在理论方面，我们计划研究使用非标准参数的内核化等主题，其中输入的一些结构方面（而不是解决方案的大小）被用作参数。其他主题包括强多项式核，图灵核，以及核化和近似性之间的联系。在实践方面，我们计划为具体问题设计核化算法，目的是实现这些算法。特别是，我们要调查的可能性ofimproving核的几个问题的平面图（除其他外）。

项目成果

Kernelization Using Structural Parameters on Sparse Graph Classes

在稀疏图类上使用结构参数进行核化

• DOI: 10.1007/978-3-642-40450-4_45
• 发表时间: 2013
• 期刊: J. Comput. Syst. Sci.
• 作者: Jakub Gajarský;Petr Hlinený;Jan Obdrzálek;Sebastian Ordyniak;Felix Reidl;Peter Rossmanith;Fernando Sánchez Villaamil;Somnath Sikdar
• 通讯作者: Somnath Sikdar

Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions

• DOI: 10.1145/2797140
• 发表时间: 2012-07
• 期刊: ACM Transactions on Algorithms (TALG)
• 作者: Eun Jung Kim;Alexander Langer;C. Paul;F. Reidl;P. Rossmanith;Ignasi Sau;S. Sikdar

Digraph width measures in parameterized algorithmics

• DOI: 10.1016/j.dam.2013.10.038
• 发表时间: 2014-05
• 期刊: Discret. Appl. Math.
• 作者: R. Ganian;Petr Hliněný;Joachim Kneis;Alexander Langer;J. Obdržálek;P. Rossmanith

Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming

宽度、深度和空间：分支和动态规划之间的权衡

• DOI: 10.3390/a11070098
• 发表时间: 2018
• 期刊: Algorithms
• 影响因子: 2.3
• 作者: Li-Hsuan Chen;Felix Reidl;Peter Rossmanith;Fernando Sánchez Villaamil
• 通讯作者: Fernando Sánchez Villaamil

A Faster Parameterized Algorithm for Treedepth

一种更快的树深度参数化算法

• DOI: 10.1007/978-3-662-43948-7_77
• 发表时间: 2014
• 作者: Felix Reidl;Peter Rossmanith;Fernando Sánchez Villaamil;Somnath Sikdar
• 通讯作者: Somnath Sikdar