Optimization Online


2-clique-bond of stable set polyhedra

Anna Galluccio (galluccio***at***iasi.cnr.it)
Claudio Gentile (gentile***at***iasi.cnr.it)
Paolo Ventura (ventura***at***iasi.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
Entry Accepted: 03/15/2011
Entry Last Modified: 04/19/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society