Approximation algorithm for minimum connected 3-path vertex cover

DOI10.1016/j.dam.2020.08.008zbMath1448.05164OpenAlexW3080897928MaRDI QIDQ2004079

Zhao Zhang, Xianyue Li, Weili Wu, Pengcheng Liu

Publication date: 14 October 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.08.008

zbMATH Keywords

approximation algorithmconnected \(k\)-path vertex cover

Mathematics Subject Classification ID

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

Related Items (1)

The k‐path vertex cover: General bounds and chordal graphs

Cites Work

• Unnamed Item
• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• On the weighted \(k\)-path vertex cover problem
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• PTAS for minimum \(k\)-path vertex cover in ball graph
• Approximate association via dissociation
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• 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
• A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
• A faster FPT algorithm for 3-path vertex cover
• Connected vertex covers in dense graphs
• The node-deletion problem for hereditary properties is NP-complete
• A unified approximation algorithm for node-deletion problems
• On approximability of connected path vertex cover
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• On the \(k\)-path vertex cover of some graph products
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Approximation algorithms for minimum weight connected 3-path vertex cover
• Hitting subgraphs in \(P_4\)-tidy graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• The vertex cover \(P_3\) problem in cubic graphs
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
• Independent packings in structured graphs
• A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs
• Node-Deletion NP-Complete Problems
• Partitioning a Graph into Small Pieces with Applications to Path Transversal

This page was built for publication: Approximation algorithm for minimum connected 3-path vertex cover