On co-bicliques
RAIRO - Operations Research (2007)
- Volume: 41, Issue: 3, page 295-304
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow 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.
- D. Cornaz and J. Fonlupt, Chromatic characterization of biclique cover. Discrete Math.306 (2006) 495–507.
- D. Cornaz and A.R. Mahjoub, The maximum induced bipartite subgraph problem with edge weights. SIAM J. on Discrete Math. to appear.
- D. Cornaz, On forests, stable sets and polyhedra associated with clique partitions. Manuscript available on Optimization Online.
- 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.
- 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.
- A. Schrijver, Combinatorial Optimization. Springer-Verlag, Berlin Heidelberg (2003).
- A. Sebő, private communication.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.