Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Clique-connecting forest and stable set polytopes

Denis Cornaz — 2010

RAIRO - Operations Research

Let be a simple undirected graph. A forest ⊆ of is said to be if each tree of spans a clique of . This paper adresses the clique-connecting forest polytope. First we give a formulation and a polynomial time separation algorithm. Then we show that the nontrivial nondegenerate facets of the stable set polytope are facets of the clique-connecting polytope. Finally we introduce a family of rank inequalities which are facets, and which generalize the clique inequalities.

On co-bicliques

Denis Cornaz — 2007

RAIRO - Operations Research

A co-biclique of a simple undirected graph is the edge-set of two disjoint complete subgraphs of . (A co-biclique is the complement of a biclique.) A subset is an independent of if there is a co-biclique such that , otherwise is a dependent of . This paper describes the minimal dependents of . (A minimal dependent is a dependent such that any proper subset of is an independent.) It is showed that a minimum-cost dependent set of can be determined in polynomial time for any nonnegative cost...

Page 1

Download Results (CSV)