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

University of Primorska
University of Leeds
Utrecht University
Czech Technical University in Prague

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
Begivenhed	International Symposium on Parameterized and Exact Computation - Amsterdam, Holland Varighed: 6 sep. 2023 → 8 sep. 2023 Konferencens nummer: 18 https://algo-conference.org/2023/ipec/

Symposium

Symposium	International Symposium on Parameterized and Exact Computation
Nummer	18
Land/Område	Holland
By	Amsterdam
Periode	06/09/2023 → 08/09/2023
Internetadresse	https://algo-conference.org/2023/ipec/

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

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). i 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Dagstuhl Publishing, Germany, International Symposium on Parameterized and Exact Computation, Amsterdam, Holland, 06/09/2023. https://doi.org/10.4230/LIPIcs.IPEC.2023.7

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

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 -