A boundary class for the \(k\)-path partition problem

DOI10.1016/j.endm.2018.05.009zbMath1453.68138OpenAlexW2807865491WikidataQ129697265 ScholiaQ129697265MaRDI QIDQ1791978

Nicholas Korpelainen

Publication date: 11 October 2018

Full work available at URL: https://doi.org/10.1016/j.endm.2018.05.009

zbMATH Keywords

boundary propertieshereditary graph classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Approximation algorithms for the directed path partition problems ⋮ A local search algorithm for the \(k\)-path partition problem ⋮ Approximating the directed path partition problem

Cites Work

• Unnamed Item
• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• The path-partition problem in bipartite distance-hereditary graphs
• \(k\)-path partitions in trees
• On the \(k\)-path partition of graphs.
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• The path partition problem and related problems in bipartite graphs

This page was built for publication: A boundary class for the \(k\)-path partition problem