On a relation between k-path partition and k-path vertex cover

DOI10.1016/J.DAM.2017.01.013zbMATH Open1464.05304OpenAlexW2592808588MaRDI QIDQ2030433FDOQ2030433

Christoph Brause, R. 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

\(k\)-path vertex coverforbidden subgraphs\(k\)-path partition

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• On the vertex \(k\)-path cover
• Independent Set in P₅-Free Graphs in Polynomial Time
• Characterizations of derived graphs
• 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
• Vertex packings: Structural properties and algorithms
• Some results on graphs without long induced paths
• The path partition problem and related problems in bipartite graphs
• The \(k\)-path vertex cover of rooted product graphs
• The complexity of dissociation set problems in graphs
• An FPT algorithm for the vertex cover \(P_4\) problem
• A Better Bound on the Variance
• \(k\)-path partitions in trees

Cited In (4)

• The geodesic-transversal problem
• Kernels for packing and covering problems
• Title not available (Why is that?)
• The k‐path vertex cover: General bounds and chordal graphs

Recommendations

• Title not available (Why is that?) 👍 👎
• On the \(k\)-path vertex cover of some graph products 👍 👎
• On the vertex \(k\)-path cover 👍 👎
• On the weighted \(k\)-path vertex cover problem 👍 👎
• The path partition problem and related problems in bipartite graphs 👍 👎
• The P k Partition Problem and Related Problems in Bipartite Graphs 👍 👎
• On the \(k\)-path partition of graphs. 👍 👎
• On the \(k\)-path partition problem in cographs 👍 👎
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs 👍 👎
• The k‐path vertex cover: General bounds and chordal graphs 👍 👎

This page was built for publication: On a relation between \(k\)-path partition and \(k\)-path vertex cover

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