Show simple item record

Treewidth is NP-Complete on Cubic Graphs

dc.contributor.authorBodlaender, Hans L.
dc.contributor.authorBonnet, Édouard
dc.contributor.authorJaffke, Lars
dc.contributor.authorKnop, Dusan
dc.contributor.authorLima, Paloma Thome de
dc.contributor.authorMilanič, Martin
dc.contributor.authorOrdyniak, Sebastian
dc.contributor.authorPandey, Sukanya
dc.contributor.authorSuchy, Ondrey
dc.date.accessioned2024-03-14T09:09:07Z
dc.date.available2024-03-14T09:09:07Z
dc.date.created2024-01-12T14:33:45Z
dc.date.issued2023
dc.identifier.issn1868-8969
dc.identifier.urihttps://hdl.handle.net/11250/3122315
dc.description.abstractIn 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.isoengen_US
dc.publisherDagstuhl Publishingen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/deed.no*
dc.titleTreewidth is NP-Complete on Cubic Graphsen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright 2023 The Autors(s)en_US
cristin.ispublishedtrue
cristin.fulltextoriginal
cristin.qualitycode1
dc.identifier.doi10.4230/LIPIcs.IPEC.2023.7
dc.identifier.cristin2225530
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.source.pagenumber7:1-7:13en_US
dc.identifier.citationLeibniz International Proceedings in Informatics. 2023, 285, 7:1-7:13.en_US
dc.source.volume285en_US


Files in this item

Thumbnail
Name:
LIPIcs.IPEC.2023.7.pdf
Size:
928.0Kb
Format:
PDF
Description:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal