The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope
Chapter
Accepted version
Permanent lenke
https://hdl.handle.net/11250/2761120Utgivelsesdato
2021Metadata
Vis full innførselSamlinger
- Department of Informatics [928]
- Registrations from Cristin [9791]
Originalversjon
In: Gentile C., Stecca G., Ventura P. (eds) Graphs and Combinatorial Optimization: from Theory to Applications. AIRO Springer Series, vol 5. pp 107-116 https://doi.org/10.1007/978-3-030-63072-0_9Sammendrag
Given an undirected graph G = (V, E) and an integer k∈{1,…,|V|} , we initiate the combinatorial study of stable sets of cardinality exactly k in G. Our aim is to instigate the polyhedral investigation of the convex hull of fixed cardinality stable sets, and we begin by introducing a large class of valid inequalities to the natural integer programming formulation of the problem.