Connected vertex covers in dense graphs
type: Item
instance of: scholarly article
title: Connected vertex covers in dense graphs
zbMATH Open document ID: 1207.68229
author: Jean Cardinal
author: Eythan Levy
published in: Theoretical Computer Science
publication date: 2010-06-07T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5717740
zbMATH Keywords: approximation algorithm
zbMATH Keywords: vertex cover
zbMATH Keywords: connected vertex cover
zbMATH Keywords: dense graph
describes a project that uses: GraPHedron
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.03.021
OpenAlex ID: W2050461440
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Depth-first search and the vertex cover problem
cites work: Complexity and Approximation Results for the Connected Vertex Cover Problem
cites work: A 2-approximation NC algorithm for connected vertex cover and tree cover
cites work: Parameterized complexity of Vertex Cover variants
cites work: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
cites work: Q4395327
cites work: An approximation of the minimum vertex cover in a graph
cites work: Computing and Combinatorics
cites work: Approximating vertex cover on dense graphs
cites work: Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
cites work: Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
cites work: Approximating the dense set-cover problem
cites work: Facet defining inequalities among graph invariants: The system graphedron
DOI: 10.1016/J.TCS.2010.03.021
description: scientific article; zbMATH DE number 5717740