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

DOI10.1007/3-540-61576-8_83MaRDI QIDQ6567680FDOQ6567680

Authors: Marc Demange, Vangelis Th. Paschos 

Publication date: 5 July 2024

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

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)

Cites Work

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

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)