Name:
Publisher version
View Source
Access full-text PDFOpen Access
View Source
Check access options
Check access options
Authors
Korpelainen, Nicholas
Affiliation
University of DerbyIssue Date
2018-06-14
Metadata
Show full item recordAbstract
We establish the first known boundary class for the k-path partition problem and deduce that for a graph class defined by finitely many minimal forbidden induced subgraphs, the k-path partition problem remains NP-hard unless one of the forbidden induced subgraphs is a subcubic tree (a tree of maximum degree at most 3) with at most one vertex of degree 3.Citation
Korpelainen, N. (2018) 'A Boundary Class for the k-Path Partition Problem', Electronic Notes in Discrete Mathematics, 67:49 .Publisher
ElsevierJournal
Electronic Notes in Discrete MathematicsDOI
10.1016/j.endm.2018.05.009Additional Links
https://linkinghub.elsevier.com/retrieve/pii/S1571065318300854Type
ArticleLanguage
enISSN
15710653ae974a485f413a2113503eed53cd6c53
10.1016/j.endm.2018.05.009
Scopus Count
Collections
The following license files are associated with this item: