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

zbMATH Keywords

independent setvertex coveringNP-complete problempolynomial time \(\rho\)-approximation algorithmquadratic programming as subproblem

Mathematics Subject Classification ID

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)

A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios

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