Parameterized algorithms of fundamental NP-hard problems: a survey
Parameterized algorithms of fundamental NP-hard problems: a survey
复制标题
基本 {NP-hard} 问题的参数化算法：调查
DOI：
10.1186/s13673-020-00226-w
复制
发表时间：
2020
影响因子：
6.6
通讯作者：
Jianxin Wang
中科院分区：
文献类型：
--
作者：
Wenjun Li;Yang Ding;Yongjie Yang;R. Simon Sherratt;Jong Hyuk Park;Jianxin Wang
摘要 参数化计算理论在过去二十年中得到了迅速发展。在理论计算机科学中，它因其理论价值和对许多实际应用的重要指导而引起了广泛的关注。我们概述了一些基本 NP 难问题的参数化算法，包括 MaxSAT、最大内部生成树、最大内部分支、平面（连通）支配集、反馈顶点集、超平面覆盖、顶点覆盖、打包和匹配问题。所有这些问题已广泛应用于物联网、无线传感器网络、人工智能、生物信息学、大数据等各个领域。本文主要关注算法的主要思想和算法技术，而省略其细节。
Abstract Parameterized computation theory has developed rapidly over the last two decades. In theoretical computer science, it has attracted considerable attention for its theoretical value and significant guidance in many practical applications. We give an overview on parameterized algorithms for some fundamental NP-hard problems, including MaxSAT, Maximum Internal Spanning Trees, Maximum Internal Out-Branching, Planar (Connected) Dominating Set, Feedback Vertex Set, Hyperplane Cover, Vertex Cover, Packing and Matching problems. All of these problems have been widely applied in various areas, such as Internet of Things, Wireless Sensor Networks, Artificial Intelligence, Bioinformatics, Big Data, and so on. In this paper, we are focused on the algorithms’ main idea and algorithmic techniques, and omit the details of them.