Abstract | ||
---|---|---|
Let XNLP be the class of parameterized prob-lems such that an instance of size $n$ with parameter $k$ can be solved nondeterministically in time $f$ ($k$) nO(1) and space f (k) log(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloringand Precoloring Extensionwith pathwidth as parameter, Sc... |
Year | DOI | Venue |
---|---|---|
2021 | 10.1109/FOCS52979.2021.00027 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Computer science,Processor scheduling,Bandwidth,Complexity theory | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hans L. Bodlaender | 1 | 5699 | 375.15 |
Carla Groenland | 2 | 0 | 0.34 |
Jesper Nederlof | 3 | 294 | 24.22 |
Céline M. F. Swennenhuis | 4 | 0 | 0.68 |