Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

Jesper Nederlof

doi:10.1007/978-3-030-42071-0_11

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

Jesper Nederlof^*

^*Corresponding author for this work

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

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.

Original language	English
Title of host publication	Treewidth, Kernels, and Algorithms
Subtitle of host publication	Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday
Editors	Fedor V. Fomin, Stefan Kratsch, Erik Jan van Leeuwen
Publisher	Springer
Pages	145-164
Number of pages	20
ISBN (Electronic)	978-3-030-42071-0
ISBN (Print)	978-3-030-42070-3
DOIs	https://doi.org/10.1007/978-3-030-42071-0_11
Publication status	Published - 2020

Publication series

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

Access to Document

10.1007/978-3-030-42071-0_11

Nederlof2020_Chapter_AlgorithmsForNP-HardProblemsViFinal published version, 427 KBLicence: Taverne

Cite this

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 (pp. 145-164). (Lecture Notes in Computer Science; Vol. 12160). Springer. https://doi.org/10.1007/978-3-030-42071-0_11

@inproceedings{b3c534dffc854d6fbc2d9993dc78f6f7,

title = "Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices",

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

author = "Jesper Nederlof",

year = "2020",

doi = "10.1007/978-3-030-42071-0_11",

language = "English",

isbn = "978-3-030-42070-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "145--164",

editor = "Fomin, {Fedor V.} and Stefan Kratsch and Leeuwen, {Erik Jan van}",

booktitle = "Treewidth, Kernels, and Algorithms",

address = "Germany",

}

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices. / Nederlof, Jesper.
Treewidth, Kernels, and Algorithms: Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. ed. / Fedor V. Fomin; Stefan Kratsch; Erik Jan van Leeuwen. Springer, 2020. p. 145-164 (Lecture Notes in Computer Science; Vol. 12160).

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

TY - GEN

T1 - Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

AU - Nederlof, Jesper

PY - 2020

Y1 - 2020

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

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

U2 - 10.1007/978-3-030-42071-0_11

DO - 10.1007/978-3-030-42071-0_11

M3 - Conference contribution

SN - 978-3-030-42070-3

T3 - Lecture Notes in Computer Science

SP - 145

EP - 164

BT - Treewidth, Kernels, and Algorithms

A2 - Fomin, Fedor V.

A2 - Kratsch, Stefan

A2 - Leeuwen, Erik Jan van

PB - Springer

ER -

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

Abstract

Publication series

Access to Document

Fingerprint

Cite this