Parameterized algorithms of fundamental NP-hard problems: a survey

Li, W. ORCID: https://orcid.org/0000-0001-6121-588X, Ding, Y., Yang, Y., Sherratt, R. S. ORCID: https://orcid.org/0000-0001-7899-4445, 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 doi: 10.1186/s13673-020-00226-w

Abstract/Summary

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
URI	https://reading-clone.eprints-hosting.org/id/eprint/91587
Identification Number/DOI	10.1186/s13673-020-00226-w
Refereed	Yes
Divisions	Life Sciences > School of Biological Sciences > Biomedical Sciences
Uncontrolled Keywords	Research, NP-hard, Parameterized complexity, FPT, W[t]-hard, AI, IoT
Publisher	Springer Berlin Heidelberg
Download/View statistics	View download statistics for this item