dc.contributor.author | Bodlaender, Hans L. | |
dc.contributor.author | Bonnet, Édouard | |
dc.contributor.author | Jaffke, Lars | |
dc.contributor.author | Knop, Dusan | |
dc.contributor.author | Lima, Paloma Thome de | |
dc.contributor.author | Milanič, Martin | |
dc.contributor.author | Ordyniak, Sebastian | |
dc.contributor.author | Pandey, Sukanya | |
dc.contributor.author | Suchy, Ondrey | |
dc.date.accessioned | 2024-03-14T09:09:07Z | |
dc.date.available | 2024-03-14T09:09:07Z | |
dc.date.created | 2024-01-12T14:33:45Z | |
dc.date.issued | 2023 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/3122315 | |
dc.description.abstract | In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Treewidth is NP-Complete on Cubic Graphs | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2023 The Autors(s) | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.IPEC.2023.7 | |
dc.identifier.cristin | 2225530 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 7:1-7:13 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2023, 285, 7:1-7:13. | en_US |
dc.source.volume | 285 | en_US |