On the weighted k-path vertex cover problem

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

Authors: Boštjan Brešar, R. Krivoš-Belluš, Gabriel Semanišin, 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

Recommendations

• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• Minimum \(k\)-path vertex cover
• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• A faster FPT algorithm for 3-path vertex cover

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

Cited In (27)

• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• 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
• The \(k\)-observer problem on \(d\)-regular graphs
• Improved approximation algorithms for path vertex covers in regular graphs
• A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem
• 3-path vertex cover and dissociation number of hexagonal graphs
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
• Approximating bounded degree deletion via matroid matching
• An efficient local search framework for the minimum weighted vertex cover problem
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• Approximating partially bounded degree deletion on directed graphs
• On a relation between \(k\)-path partition and \(k\)-path vertex cover
• TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$
• The geodesic-transversal problem
• Minimum \(k\)-path vertex cover
• An FPT algorithm for the vertex cover \(P_4\) problem
• Complexity of the maximum \(k\)-path vertex cover problem
• On the minimum vertex \(k\)-path cover of trees
• 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
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• The k‐path vertex cover: General bounds and chordal graphs

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)