2-clique-bond of stable set polyhedra
Anna Galluccio (galluccioiasi.cnr.it)
Abstract: The 2-bond is a generalization of the 2-join where the subsets of nodes that are connected on each shore of the partition are not necessarily disjoint. If all the subsets are cliques we say that the 2-bond is a 2-clique-bond. We consider a graph G obtained as the 2-clique-bond of two graphs G1 and G2 and we study the polyhedral properties of the stable set polytope associated with this graph. In particular, we prove that a linear description of the stable set polytope of G is obtained by properly composing the linear inequalities describing the stable set polytopes of four graphs that are related to G1 and G2. We show how to apply the 2-clique-bond composition to provide the complete linear description of large classes of graphs.
Keywords: Stable set polytope, graph compositions, 2-join, polyhedral combinatorics.
Category 1: Combinatorial Optimization (Polyhedra )
Category 2: Integer Programming (0-1 Programming )
Citation: A preliminary version of this paper appeared as G. Galluccio, C. Gentile, P.Ventura, 2-clique-bond of stable set polyhedra, Tech. Rep. 09-10, IASI-CNR, 2009.
Entry Submitted: 03/15/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|