A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set

DOI10.1051/RO/1994280404131zbMath0857.90130OpenAlexW2285066217MaRDI QIDQ4887135

Vangelis Th. Paschos

Publication date: 20 February 1997

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/105093

zbMATH Keywords

set coveringNP-completeindependent set problemconstant-ratio-polynomial-time-approximation-algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

This page was built for publication: A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set