On the weighted k-path vertex cover problem

DOI10.1016/J.DAM.2014.05.042zbMATH Open1297.05103OpenAlexW2038294264MaRDI QIDQ406316FDOQ406316

Gabriel Semanišin, R. 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 algorithmvertex coverweighted graph

Mathematics Subject Classification ID

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

Cites Work

• 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 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 F-independence in graphs
• Node-Deletion Problems on Bipartite Graphs
• A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover

Cited In (22)

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

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

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