From the W-hierarchy to XNLP: Classes of Fixed Parameter Intractability
Publication date
2022-02-22
Authors
Bodlaender, Hans L.
Editors
Mutzel, Petra
Rahman, Md. Saidur
Slamin
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
In this short survey, a number of old and new notions from parameterized complexity are discussed. We start with looking at the W-hierarchy, including the classes W[1], W[2], W[P]. Then, a recent development where problems are shown to be complete for simultaneously non-deterministic time of the form f(k) nc and space of the form f(k) log n, is discussed. Some consequences and other notions are briefly explored.
Keywords
Parameterized complexity, W-hierarchy, XNLP, XP, Taverne, Theoretical Computer Science, General Computer Science
Citation
Bodlaender, H L 2022, From the W-hierarchy to XNLP : Classes of Fixed Parameter Intractability. in P Mutzel, M S Rahman & Slamin (eds), WALCOM: Algorithms and Computation : 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24–26, 2022, Proceedings. 1 edn, Lecture Notes in Computer Science, vol. 13174 , Springer, Cham, pp. 15-25, 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022, Jember, Indonesia, 24/03/22. https://doi.org/10.1007/978-3-030-96731-4_2, conference