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

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
Event	International Symposium on Parameterized and Exact Computation - Amsterdam, Netherlands Duration: 6 Sept 2023 → 8 Sept 2023 Conference number: 18 https://algo-conference.org/2023/ipec/

Symposium

Symposium	International Symposium on Parameterized and Exact Computation
Number	18
Country/Territory	Netherlands
City	Amsterdam
Period	06/09/2023 → 08/09/2023
Internet address	https://algo-conference.org/2023/ipec/

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

note = " International Symposium on Parameterized and Exact Computation, IPEC ; Conference date: 06-09-2023 Through 08-09-2023",

url = "https://algo-conference.org/2023/ipec/",

}

Bodlaender, H, Bonnet, É, Jaffke, L, Knop, D, Thomé de Lima, P, Milanič, M, Ordyniak, S, Pandey, S & Suchý, O 2023, Treewidth is NP-complete on cubic graphs (and related results). in 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Dagstuhl Publishing, Germany, International Symposium on Parameterized and Exact Computation, Amsterdam, Netherlands, 06/09/2023. https://doi.org/10.4230/LIPIcs.IPEC.2023.7

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

N1 - Conference code: 18

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

T2 - International Symposium on Parameterized and Exact Computation

Y2 - 6 September 2023 through 8 September 2023

ER -