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

zbMATH Keywords

graph algorithmvertex coverweighted graph

Mathematics Subject Classification ID

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

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

Cites work

• A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Minimum \(k\)-path vertex cover
• Node-Deletion Problems on Bipartite Graphs
• On \({\mathcal F}\)-independence in graphs
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the \(k\)-path vertex cover of some graph products
• On the vertex \(k\)-path cover
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs

Cited in

(27)

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