Improved non-approximability results for minimum vertex cover with density constraints
type: Item
instance of: scholarly article
title: Improved non-approximability results for minimum vertex cover with density constraints
zbMATH Open document ID: 0933.68101
DOI: 10.1016/S0304-3975(97)00226-0
author: Andrea Clementi
author: Luca Trevisan
published in: Theoretical Computer Science
publication date: 2000-01-12T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1387545
zbMATH Keywords: computational complexity
zbMATH Keywords: approximation algorithms
zbMATH Keywords: vertex cover
zbMATH Keywords: expander graphs
MaRDI profile type: Publication
cites work: Derandomized graph products
cites work: Q4234075
cites work: Q4230322
cites work: Q4230321
cites work: Efficient probabilistically checkable proofs and applications to approximations
cites work: Improved non-approximability results
cites work: The Steiner problem with edge lengths 1 and 2
cites work: Completeness in approximation classes
cites work: Q4470516
cites work: Q4228484
cites work: Two prover protocols, low error at affordable rates
cites work: Explicit constructions of linear-sized superconcentrators
cites work: Some simplified NP-complete graph problems
cites work: Q4198056
cites work: Q4228449
cites work: Q4526964
cites work: On the approximation of shortest common supersequences and longest common subsequences
cites work: Q4142699
cites work: Ramanujan graphs
cites work: On the hardness of approximating minimization problems
cites work: Q3322143
cites work: Q4856179
cites work: Optimization, approximation, and complexity classes
cites work: Q4234093
cites work: Expanders, randomness, or time versus space
Recommended article: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
Recommended article: Q4952635
Recommended article: Improved approximation of maximum vertex cover
Recommended article: Q2712300
Recommended article: Q4411285
Recommended article: Improved Parameterized Upper Bounds for Vertex Cover
Recommended article: An improved approximation algorithm for vertex cover with hard capacities
Recommended article: Q4448746
Recommended article: On the hardness of approximating minimum vertex cover
Recommended article: Q4449173
description: scientific article; zbMATH DE number 1387545