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ý

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Original language	English
Title of host publication	18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Publisher	Dagstuhl Publishing, Germany
Publication date	2023
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2023.7
Publication status	Published - 2023

Access to Document

10.4230/LIPIcs.IPEC.2023.7Licence: CC BY

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

Cite this

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

}

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 -