On a relation between \(k\)-path partition and \(k\)-path vertex cover

DOI10.1016/j.dam.2017.01.013zbMath1464.05304OpenAlexW2592808588MaRDI QIDQ2030433

Christoph Brause, Rastislav Krivoš-Belluš

Publication date: 7 June 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.01.013

zbMATH Keywords

forbidden subgraphs\(k\)-path vertex cover\(k\)-path partition

Mathematics Subject Classification ID

Combinatorial optimization (90C27) 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

Unnamed Item ⋮ The k‐path vertex cover: General bounds and chordal graphs ⋮ The geodesic-transversal problem ⋮ Kernels for packing and covering problems

Cites Work

• Unnamed Item
• Unnamed Item
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• An FPT algorithm for the vertex cover \(P_4\) problem
• Some results on graphs without long induced paths
• \(k\)-path partitions in trees
• On the \(k\)-path vertex cover of some graph products
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• The \(k\)-path vertex cover of rooted product graphs
• On the vertex \(k\)-path cover
• The path partition problem and related problems in bipartite graphs
• A Better Bound on the Variance
• Vertex packings: Structural properties and algorithms
• Independent Set in P₅-Free Graphs in Polynomial Time
• Characterizations of derived graphs