The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope

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 v...

Full description

Saved in:
Bibliographic Details
Main Authors: Lallo Dias, Phillippe Samer, Haugland, Dag
Format: Book
Language:English
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.