Constructive -- non-constructive approximation and maximum independent set problem

DOI10.1007/3-540-61576-8_83MaRDI QIDQ6567680zbMATH OpenFDO

Authors Marc Demange, Vangelis Th. Paschos

Publication date 5 July 2024

zbMATH Keywords

maximum independent setoptimal objective value

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• On the complexity of approximating the independent set problem
• Constructing concrete hard instances of the maximum independent set problem
• On the complexity of approximating the independent set problem (extended abstract)
• The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
• scientific article; zbMATH DE number 1405687

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Approximate solution of NP optimization problems
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Node-weighted graphs having the König-Egerváry property
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
• Vertex packings: Structural properties and algorithms

This page was built for publication: Constructive -- non-constructive approximation and maximum independent set problem

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