核心化算法中的新技术研究

项目名称： 核心化算法中的新技术研究

项目编号： No.61772115

项目类型： 面上项目

立项/批准年度： 2018

项目学科： 自动化技术、计算机技术

项目作者： 肖鸣宇

作者单位： 电子科技大学

项目金额： 16万元

中文摘要： 核心化算法是目前参数计算理论中非常活跃的一个研究分支。本项目主要对“基于极值图论的思想进行核心化算法设计”和“新的核心化模型”这两个问题进行探索性研究。探索那些类型的问题易于利用极值图论思想来进行核心算法设计，并解决平面图上一些具体的核心化问题。同时研究近似核心化这种模型的可行性和实用性。为今后进一步研究核心化算法打下基础。

中文关键词： 核心化；固定参数算法；极值图论；近似核心化；NP-难问题

英文摘要： Kernelizaiton is one of the most active branches in parameterized algorithms. This project will focus on how to use the idea of “extremal graph theory” and “approximation kernelization” to design kernelizaiton algorithms. In details, we will investigate for which problems we can use extremal graph theory to design kernelization algorithms, and study kernelizations for some problems in planar graphs. The project will also investigate the possibility of the approximation kernelization model. These lay a foundation for our further research on kernelization algorithms.

英文关键词： Kernelization;FPT;Extremal graph theory;Lossy kernelization;NP-hard problems