Treewidth is NP-complete on cubic graphs (and related results)

Hans Bodlaender; Édouard Bonnet; Lars Jaffke; Dusan Knop; Paloma Thomé de Lima; Martin Milanič; Sebastian Ordyniak; Sukanya Pandey; Ondřej Suchý

doi:10.4230/LIPIcs.IPEC.2023.7

Treewidth is NP-complete on cubic graphs (and related results)

Hans Bodlaender
, Édouard Bonnet
, Lars Jaffke
, Dusan Knop
, Paloma Thomé de Lima
, Martin Milanič
, Sebastian Ordyniak
, Sukanya Pandey
, Ondřej Suchý

Algorithms

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

Originalsprog	Engelsk
Titel	18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Forlag	Dagstuhl Publishing, Germany
Publikationsdato	2023
DOI	https://doi.org/10.4230/LIPIcs.IPEC.2023.7
Status	Udgivet - 2023

Adgang til dokumentet

10.4230/LIPIcs.IPEC.2023.7Licens: CC BY

https://drops.dagstuhl.de/storage/00lipics/lipics-vol285-ipec2023/LIPIcs.IPEC.2023.7/LIPIcs.IPEC.2023.7.pdfLicens: CC BY

Citationsformater

@inproceedings{648e83efa77c4d30aa4e3f6472b37bd2,

title = "Treewidth is NP-complete on cubic graphs (and related results)",

author = "Hans Bodlaender and {\'E}douard Bonnet and Lars Jaffke and Dusan Knop and \{Thom{\'e} de Lima\}, Paloma and Martin Milani{\v c} and Sebastian Ordyniak and Sukanya Pandey and Ond{\v r}ej Such{\'y}",

year = "2023",

doi = "10.4230/LIPIcs.IPEC.2023.7",

language = "English",

booktitle = "18th International Symposium on Parameterized and Exact Computation (IPEC 2023)",

publisher = "Dagstuhl Publishing, Germany",

}

Treewidth is NP-complete on cubic graphs (and related results). / Bodlaender, Hans; Bonnet, Édouard; Jaffke, Lars et al.
18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Dagstuhl Publishing, Germany, 2023.

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Treewidth is NP-complete on cubic graphs (and related results)

AU - Bodlaender, Hans

AU - Bonnet, Édouard

AU - Jaffke, Lars

AU - Knop, Dusan

AU - Thomé de Lima, Paloma

AU - Milanič, Martin

AU - Ordyniak, Sebastian

AU - Pandey, Sukanya

AU - Suchý, Ondřej

PY - 2023

Y1 - 2023

U2 - 10.4230/LIPIcs.IPEC.2023.7

DO - 10.4230/LIPIcs.IPEC.2023.7

M3 - Article in proceedings

BT - 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

PB - Dagstuhl Publishing, Germany

ER -