1 citations · 1 across the 3 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2010★ 1 cited
Approximating Vertex Cover in Dense Hypergraphs
Jean Cardinal, Marek Karpinski, Richard Schmied +1
We consider the minimum vertex cover problem in hypergraphs in which every hyperedge has size k (also known as minimum hitting set problem, or minimum set cover with element freque…
cs.DS2010
Approximating Subdense Instances of Covering Problems
Jean Cardinal, Marek Karpinski, Richard Schmied +1
We study approximability of subdense instances of various covering problems on graphs, defined as instances in which the minimum or average degree is Omega(n/psi(n)) for some funct…