Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
Publication date
2020
Authors
Nederlof, Jesper
Editors
Fomin, Fedor V.
Kratsch, Stefan
Leeuwen, Erik Jan van
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
We survey a number of recent results that relate the fine-grained complexity of several NP-Hard problems with the rank of certain matrices. The main technical theme is that for a wide variety of Divide & Conquer algorithms, structural insights on associated partial solutions matrices may directly lead to speedups.
Keywords
Taverne
Citation
Nederlof, J 2020, Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices. in F V Fomin, S Kratsch & E J V Leeuwen (eds), Treewidth, Kernels, and Algorithms : Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 12160, Springer, pp. 145-164. https://doi.org/10.1007/978-3-030-42071-0_11