Accessibility navigation

Parameterized algorithms of fundamental NP-hard problems: a survey

Li, W. ORCID:, Ding, Y., Yang, Y., Sherratt, R. S., Park, J. H. and Wang, J. (2020) Parameterized algorithms of fundamental NP-hard problems: a survey. Human-centric Computing and Information Sciences, 10 (1). 29. ISSN 2192-1962

Text (Open Access) - Published Version
· Available under License Creative Commons Attribution.
· Please see our End User Agreement before downloading.


It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1186/s13673-020-00226-w


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.

Item Type:Article
Divisions:Life Sciences > School of Biological Sciences > Biomedical Sciences
ID Code:91587
Uncontrolled Keywords:Research, NP-hard, Parameterized complexity, FPT, W[t]-hard, AI, IoT
Publisher:Springer Berlin Heidelberg


Downloads per month over past year

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation