Approximation algorithm for minimum connected 3-path vertex cover
type: Item
instance of: scholarly article
title: Approximation algorithm for minimum connected 3-path vertex cover
zbMATH Open document ID: 1448.05164
author: Pengcheng Liu
author: Zhao Zhang
author: Xianyue Li
author: Weili Wu
published in: Discrete Applied Mathematics
publication date: 2020-10-14T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7260820
zbMATH Keywords: connected \(k\)-path vertex cover
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
full work available at URL: j.dam.2020.08.008
OpenAlex ID: W3080897928
cites work: Q5463498
cites work: Minimum \(k\)-path vertex cover
cites work: Hitting subgraphs in \(P_4\)-tidy graphs
cites work: On the weighted \(k\)-path vertex cover problem
cites work: Independent packings in structured graphs
cites work: Connected vertex covers in dense graphs
cites work: Fixed-parameter algorithms for Vertex Cover \(P_3\)
cites work: A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
cites work: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
cites work: A unified approximation algorithm for node-deletion problems
cites work: On approximability of connected path vertex cover
cites work: On the \(k\)-path vertex cover of some graph products
cites work: On computing the minimum 3-path vertex cover and dissociation number of graphs
cites work: A faster FPT algorithm for 3-path vertex cover
cites work: Node-Deletion NP-Complete Problems
cites work: Partitioning a Graph into Small Pieces with Applications to Path Transversal
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: A 2-approximation algorithm for the vertex coverP4problem in cubic graphs
cites work: Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
cites work: PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
cites work: The complexity of dissociation set problems in graphs
cites work: Approximation algorithms for minimum weight connected 3-path vertex cover
cites work: A fixed-parameter algorithm for the vertex cover \(P_3\) problem
cites work: The vertex cover \(P_3\) problem in cubic graphs
cites work: A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
cites work: A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
cites work: Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
cites work: Approximate association via dissociation
cites work: PTAS for minimum \(k\)-path vertex cover in ball graph
cites work: Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
DOI: 10.1016/J.DAM.2020.08.008
description: scientific article; zbMATH DE number 7260820