On co-bicliques

Denis Cornaz

RAIRO - Operations Research (2007)

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

Abstract

top
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 + E . Based on this, we obtain a branch-and-cut algorithm for the maximum co-biclique problem which is, given a weight vector w + E , to find a co-biclique B of G maximizing w(B) = ∑e∈B we.

How to cite

top

Cornaz, 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
  1. D. Cornaz, A linear programming formulation for the maximum complete multipartite subgraph problem. Math. Program. B105 (2006) 329–344.  Zbl1079.05093
  2. D. Cornaz and J. Fonlupt, Chromatic characterization of biclique cover. Discrete Math.306 (2006) 495–507.  Zbl1087.05043
  3. D. Cornaz and A.R. Mahjoub, The maximum induced bipartite subgraph problem with edge weights. SIAM J. on Discrete Math. to appear.  Zbl1141.05076
  4. D. Cornaz, On forests, stable sets and polyhedra associated with clique partitions. Manuscript available on Optimization Online.  Zbl1221.05132
  5. V. Jost, Ordonnancement chromatique : polyèdres, complexité et classification. Thèse de l'Université Joseph Fourier, Grenoble (2006).  
  6. M. Grötschel, L. Lovàsz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica1 (1981) 169–197.  Zbl0492.90056
  7. 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
  8. A. Schrijver, Combinatorial Optimization. Springer-Verlag, Berlin Heidelberg (2003).  Zbl1041.90001
  9. A. Sebő, private communication.  

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.