Approximation algorithms for minimum weight connected 3-path vertex cover
type: Item
instance of: scholarly article
title: Approximation algorithms for minimum weight connected 3-path vertex cover
zbMATH Open document ID: 1428.05297
author: Yingli Ran
author: Zhao Zhang
author: X. Li
author: Du Ding-Zhu
author: Xiaohui Huang
published in: Applied Mathematics and Computation
publication date: 2019-11-26T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 7136563
zbMATH Keywords: connected \(k\)-path vertex cover
zbMATH Keywords: weight
zbMATH Keywords: approximation algorithm
zbMATH Keywords: non-submodular potential function
MaRDI profile type: Publication
full work available at URL: j.amc.2018.11.045
OpenAlex ID: W2903563585
cites work: Minimum \(k\)-path vertex cover
cites work: On the weighted \(k\)-path vertex cover problem
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: Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
cites work: A unified approximation algorithm for node-deletion problems
cites work: On approximability of connected path vertex cover
cites work: On approximability of the independent/connected edge dominating set problems
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: Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
cites work: A 2-approximation algorithm for the vertex coverP4problem in cubic graphs
cites work: PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
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: A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
cites work: A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
cites work: Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
cites work: Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
DOI: 10.1016/J.AMC.2018.11.045
Recommended article: Approximation algorithm for minimum connected 3-path vertex cover
Recommended article: Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
Recommended article: Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem
Recommended article: Q2991224
Recommended article: On approximability of connected path vertex cover
Recommended article: Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight
Recommended article: Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
Recommended article: Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
Recommended article: Parameterized algorithm for 3-path vertex cover
Recommended article: On computing the minimum 3-path vertex cover and dissociation number of graphs
description: scientific article; zbMATH DE number 7136563