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

DOI10.1051/RO/1994280404131MaRDI QIDQ4887135zbMATH OpenOpenAlexFDO

Authors 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

constant-ratio-polynomial-time-approximation-algorithmindependent set problemNP-completeset covering

Mathematics Subject Classification ID

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

Recommendations

• The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
• On approximation problems related to the independent set and vertex cover problems
• scientific article; zbMATH DE number 563689
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• New approximation algorithms for the vertex cover problem

Cited in

(3)

• The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
• Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
• scientific article; zbMATH DE number 5056647 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4887135)