The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
DOI10.1023/A:1008660812834zbMath0872.90106OpenAlexW1539745397MaRDI QIDQ1356067
Marc Demange, Vangelis Th. Paschos
Publication date: 4 June 1997
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/a:1008660812834
independent setvertex coveringNP-complete problempolynomial time \(\rho\)-approximation algorithmquadratic programming as subproblem
Programming involving graphs or networks (90C35) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (1)
This page was built for publication: The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems