Efficient algorithm for the vertex cover P_k problem on cacti

DOI10.1016/J.AMC.2017.05.034MaRDI QIDQ1739987zbMATH OpenOpenAlexFDO

Authors Jianhua 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

cactus graphefficient algorithmvertex cover \(P_k\) problem

Mathematics Subject Classification ID

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

Recommendations

• On the \(k\)-path cover problem for cacti
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• The vertex cover \(P_3\) problem in cubic graphs
• An FPT algorithm for the vertex cover \(P_4\) problem

Cites work

• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• 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
• Graph theory
• Minimum \(k\)-path vertex cover
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the \(k\)-path cover problem for cacti
• On the weighted \(k\)-path vertex cover problem
• Optimal covering of cacti by vertex-disjoint paths

Cited in

(7)

• Hitting subgraphs in \(P_4\)-tidy graphs
• On the vertex separation of cactus graphs
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• Minimum cost edge subset covering exactly \(k\) vertices of a graph
• An FPT algorithm for the vertex cover \(P_4\) problem
• A survey on vertex cover \({P_k}\) problem
• On the \(k\)-path cover problem for cacti

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

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