Abstract
Parallel parameterized complexity theory studies how fixed-parameter tractable (fpt) problems can be solved in parallel. Previous theoretical work focused on parallel algorithms that are very fast in principle, but did not take into account that when we only have a small number of processors (between 2 and, say, 1024), it is more important that the parallel algorithms are work-efficient. In the present paper we investigate how work-efficient fpt algorithms can be designed. We review standard methods from fpt theory, like kernelization, search trees, and interleaving, and prove trade-offs for them between work efficiency and runtime improvements. This results in a toolbox for developing work-efficient parallel fpt algorithms.
| Original language | English |
|---|---|
| Title of host publication | WALCOM 2019: WALCOM: Algorithms and Computation |
| Editors | Gautam K. Das, Partha S. Mandal, Krishnendu Mukhopadhyaya , Shin-ichi Nakano |
| Number of pages | 13 |
| Volume | 11355 LNCS |
| Publisher | Springer, Cham |
| Publication date | 21.12.2018 |
| Pages | 341-353 |
| ISBN (Print) | 978-3-030-10563-1 |
| ISBN (Electronic) | 978-3-030-10564-8 |
| DOIs | |
| Publication status | Published - 21.12.2018 |
| Event | 13th International Conference and Workshop on Algorithms and Computations - Guwahati, India Duration: 27.02.2019 → 02.03.2019 Conference number: 224069 |
DFG Research Classification Scheme
- 4.43-01 Theoretical Computer Science
