From the W-hierarchy to XNLP: Classes of Fixed Parameter Intractability

Hans L. Bodlaender

doi:10.1007/978-3-030-96731-4_2

From the W-hierarchy to XNLP: Classes of Fixed Parameter Intractability

Hans L. Bodlaender^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

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) n^c and space of the form f(k) log n, is discussed. Some consequences and other notions are briefly explored.

Original language	English
Title of host publication	WALCOM: Algorithms and Computation
Subtitle of host publication	16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24–26, 2022, Proceedings
Editors	Petra Mutzel, Md. Saidur Rahman, Slamin
Place of Publication	Cham
Publisher	Springer
Pages	15-25
Number of pages	11
Edition	1
ISBN (Electronic)	978-3-030-96731-4
ISBN (Print)	978-3-030-96730-7
DOIs	https://doi.org/10.1007/978-3-030-96731-4_2
Publication status	Published - 22 Feb 2022
Event	16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022 - Jember, Indonesia Duration: 24 Mar 2022 → 26 Mar 2022

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	13174
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022
Country/Territory	Indonesia
City	Jember
Period	24/03/22 → 26/03/22

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

Keywords

Parameterized complexity
W-hierarchy
XNLP
XP

Access to Document

10.1007/978-3-030-96731-4_2

Bodlaender2022_Chapter_FromTheW-hierarchyToXNLPFinal published version, 237 KBLicence: Taverne

Cite this

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 ed., pp. 15-25). (Lecture Notes in Computer Science; Vol. 13174 ). Springer. https://doi.org/10.1007/978-3-030-96731-4_2

Bodlaender, Hans L. / From the W-hierarchy to XNLP : Classes of Fixed Parameter Intractability. WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24–26, 2022, Proceedings. editor / Petra Mutzel ; Md. Saidur Rahman ; Slamin. 1. ed. Cham : Springer, 2022. pp. 15-25 (Lecture Notes in Computer Science).

@inproceedings{1ae48d5481444f47a1797fd15c8cdf6c,

title = "From the W-hierarchy to XNLP: Classes of Fixed Parameter Intractability",

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",

author = "Bodlaender, {Hans L.}",

note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022 ; Conference date: 24-03-2022 Through 26-03-2022",

year = "2022",

month = feb,

day = "22",

doi = "10.1007/978-3-030-96731-4_2",

language = "English",

isbn = "978-3-030-96730-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "15--25",

editor = "Petra Mutzel and Rahman, {Md. Saidur} and Slamin",

booktitle = "WALCOM: Algorithms and Computation",

edition = "1",

}

Bodlaender, HL 2022, From the W-hierarchy to XNLP: Classes of Fixed Parameter Intractability. in P Mutzel, MS 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

From the W-hierarchy to XNLP: Classes of Fixed Parameter Intractability. / Bodlaender, Hans L.
WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24–26, 2022, Proceedings. ed. / Petra Mutzel; Md. Saidur Rahman; Slamin. 1. ed. Cham: Springer, 2022. p. 15-25 (Lecture Notes in Computer Science; Vol. 13174 ).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - From the W-hierarchy to XNLP

T2 - 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022

AU - Bodlaender, Hans L.

PY - 2022/2/22

Y1 - 2022/2/22

N2 - 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.

AB - 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.

KW - Parameterized complexity

KW - W-hierarchy

KW - XNLP

KW - XP

UR - http://www.scopus.com/inward/record.url?scp=85127840522&partnerID=8YFLogxK

UR - https://rdcu.be/cMjdb

U2 - 10.1007/978-3-030-96731-4_2

DO - 10.1007/978-3-030-96731-4_2

M3 - Conference contribution

AN - SCOPUS:85127840522

SN - 978-3-030-96730-7

T3 - Lecture Notes in Computer Science

SP - 15

EP - 25

BT - WALCOM: Algorithms and Computation

A2 - Mutzel, Petra

A2 - Rahman, Md. Saidur

A2 - Slamin, null

PB - Springer

CY - Cham

Y2 - 24 March 2022 through 26 March 2022

ER -

Bodlaender HL. From the W-hierarchy to XNLP: Classes of Fixed Parameter Intractability. In Mutzel P, Rahman MS, Slamin, editors, WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24–26, 2022, Proceedings. 1 ed. Cham: Springer. 2022. p. 15-25. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-96731-4_2

From the W-hierarchy to XNLP: Classes of Fixed Parameter Intractability

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this