On the weighted \(k\)-path vertex cover problem

DOI10.1016/j.dam.2014.05.042zbMath1297.05103OpenAlexW2038294264MaRDI QIDQ406316

Gabriel Semanisin, Rastislav Krivoš-Belluš, Boštjan Brešar, Petra Šparl

Publication date: 8 September 2014

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

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

zbMATH Keywords

graph algorithmweighted graphvertex cover

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items

Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover ⋮ Approximating Bounded Degree Deletion via Matroid Matching ⋮ Unnamed Item ⋮ On the vertex cover \(P_3\) problem parameterized by treewidth ⋮ The k‐path vertex cover: General bounds and chordal graphs ⋮ A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs ⋮ An FPT algorithm for the vertex cover \(P_4\) problem ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Efficient algorithm for the vertex cover \(P_k\) problem on cacti ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ The geodesic-transversal problem ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Improved approximation algorithms for path vertex covers in regular graphs ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover ⋮ An efficient local search framework for the minimum weighted vertex cover problem ⋮ The k-Observer Problem on d-regular Graphs ⋮ Algorithm for online 3-path vertex cover ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs ⋮ 3-path vertex cover and dissociation number of hexagonal graphs

Cites Work

• 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
• 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
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• On the vertex \(k\)-path cover
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• On F-independence in graphs
• A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
• Node-Deletion Problems on Bipartite Graphs

This page was built for publication: On the weighted \(k\)-path vertex cover problem