A boundary class for the k-path partition problem

DOI10.1016/J.ENDM.2018.05.009zbMATH Open1453.68138OpenAlexW2807865491WikidataQ129697265 ScholiaQ129697265MaRDI QIDQ1791978FDOQ1791978

Authors: Nicholas Korpelainen 

Publication date: 11 October 2018

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

Recommendations

• On the \(k\)-path partition problem in cographs
• On the \(k\)-path partition of graphs.
• NP-hard graph problems and boundary classes of graphs
• The path partition problem and related problems in bipartite graphs
• The P k Partition Problem and Related Problems in Bipartite Graphs

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• 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
• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• The path-partition problem in bipartite distance-hereditary graphs
• On the \(k\)-path partition of graphs.
• \(k\)-path partitions in trees

Cited In (5)

• Approximation algorithms for the directed path partition problems
• A local search algorithm for the \(k\)-path partition problem
• Approximating the directed path partition problem
• Improved approximation algorithms for the \(k\)-path partition problem
• On the \(k\)-path partition problem in cographs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1791978)