# On co-bicliques

RAIRO - Operations Research (2007)

- Volume: 41, Issue: 3, page 295-304
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topCornaz, Denis. "On co-bicliques." RAIRO - Operations Research 41.3 (2007): 295-304. <http://eudml.org/doc/250139>.

@article{Cornaz2007,

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.
},

author = {Cornaz, Denis},

journal = {RAIRO - Operations Research},

keywords = {Co-bicyclique; signed graph; branch-and-cut},

language = {eng},

month = {8},

number = {3},

pages = {295-304},

publisher = {EDP Sciences},

title = {On co-bicliques},

url = {http://eudml.org/doc/250139},

volume = {41},

year = {2007},

}

TY - JOUR

AU - Cornaz, Denis

TI - On co-bicliques

JO - RAIRO - Operations Research

DA - 2007/8//

PB - EDP Sciences

VL - 41

IS - 3

SP - 295

EP - 304

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

LA - eng

KW - Co-bicyclique; signed graph; branch-and-cut

UR - http://eudml.org/doc/250139

ER -

## References

top- D. Cornaz, A linear programming formulation for the maximum complete multipartite subgraph problem. Math. Program. B105 (2006) 329–344. Zbl1079.05093
- D. Cornaz and J. Fonlupt, Chromatic characterization of biclique cover. Discrete Math.306 (2006) 495–507. Zbl1087.05043
- D. Cornaz and A.R. Mahjoub, The maximum induced bipartite subgraph problem with edge weights. SIAM J. on Discrete Math. to appear. Zbl1141.05076
- D. Cornaz, On forests, stable sets and polyhedra associated with clique partitions. Manuscript available on Optimization Online. Zbl1221.05132
- V. Jost, Ordonnancement chromatique : polyèdres, complexité et classification. Thèse de l'Université Joseph Fourier, Grenoble (2006).
- M. Grötschel, L. Lovàsz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica1 (1981) 169–197. Zbl0492.90056
- D. Monson, N.J. Pullman and R. Rees, A survey of clique and biclique coverings and factorizations of (0,1)-matrices. Bull. I.C.A.14 (1995) 17–86. Zbl0832.05088
- A. Schrijver, Combinatorial Optimization. Springer-Verlag, Berlin Heidelberg (2003). Zbl1041.90001
- A. Sebő, private communication.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.