Efficient algorithm for the vertex cover \(P_k\) problem on cacti

DOI10.1016/j.amc.2017.05.034zbMath1426.05169OpenAlexW2615367498MaRDI QIDQ1739987

Jian-hua Tu

Publication date: 29 April 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2017.05.034

zbMATH Keywords

efficient algorithmcactus graphvertex cover \(P_k\) problem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Hitting subgraphs in \(P_4\)-tidy graphs

Cites Work

• Unnamed Item
• On the weighted \(k\)-path vertex cover problem
• 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
• Optimal covering of cacti by vertex-disjoint paths
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Combinatorial algorithms on a class of graphs
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• On the \(k\)-path cover problem for cacti
• A linear-time approximation algorithm for the weighted vertex cover problem
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem

This page was built for publication: Efficient algorithm for the vertex cover \(P_k\) problem on cacti