No CrossRef data available.
Article contents
On co-bicliques
Published online by Cambridge University Press: 21 August 2007
Abstract
A co-biclique of a simple undirected graph G = (V,E) is the edge-set of two disjoint complete subgraphs of G.(A co-biclique is the complement of a biclique.)A subset F ⊆ E is an independent of G if there is a co-biclique B such that F ⊆ B, otherwise F is a dependent of G. This paper describes the minimal dependents of G. (A minimal dependent is a dependent C such that any proper subset of C is an independent.) It is showed that a minimum-cost dependent set of G can be determined in polynomial time for any nonnegative cost vector $x\in \mathbb Q_+^E$ . Based on this, we obtain a branch-and-cut algorithm for the maximum co-biclique problem which is, given a weight vector $w\in \mathbb Q_+^E$ , to find a co-biclique B of G maximizing w(B) = ∑e∈B we .
- Type
- Research Article
- Information
- RAIRO - Operations Research , Volume 41 , Issue 3: Journées Polyèdres et Optimisation Combinatoire , July 2007 , pp. 295 - 304
- Copyright
- © EDP Sciences, ROADEF, SMAI, 2007