A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
type: Item
instance of: scholarly article
title: A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
zbMATH Open document ID: 1260.68304
author: Wenli Zhou
author: Jianhua Tu
published in: Information Processing Letters
publication date: 2013-04-04T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6150423
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: approximation algorithm
zbMATH Keywords: vertex cover \(P_n\) problem
MaRDI profile type: Publication
full work available at URL: j.ipl.2011.04.009
OpenAlex ID: W1968635621
cites work: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
cites work: A linear-time approximation algorithm for the weighted vertex cover problem
cites work: Q5422499
cites work: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
cites work: Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
cites work: Primal-dual approximation algorithms for feedback problems in planar graphs
cites work: A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
DOI: 10.1016/J.IPL.2011.04.009
Recommended article: A fixed-parameter algorithm for the vertex cover \(P_3\) problem
Recommended article: Fixed-parameter algorithms for Vertex Cover \(P_3\)
Recommended article: A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
Recommended article: An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
Recommended article: Q3322143
Recommended article: A 2-approximation algorithm for the vertex coverP4problem in cubic graphs
Recommended article: An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth
Recommended article: Approximation algorithms for the partition vertex cover problem
Recommended article: Approximation Algorithms for the Partition Vertex Cover Problem
Recommended article: On the Approximability of the Vertex Cover and Related Problems
description: scientific article; zbMATH DE number 6150423