TY - JOUR

T1 - Solving the maximum edge biclique packing problem on unbalanced bipartite graphs

AU - Acuña, V.

AU - Ferreira, C. E.

AU - Freire, A. S.

AU - Moreno, E.

N1 - Funding Information:
We thank the STIC-Amsud project, Anillo project ACT-88, CAPES and CNPq (Proc. No. 302736/2010-7 and 201036/2010-0 ) for supporting part of this research.

PY - 2014

Y1 - 2014

N2 - A biclique is a complete bipartite graph. Given an (L,R)-bipartite graph G=(V,E) and a positive integer k, the maximum edge biclique packing (MEBP) problem consists in finding a set of at most k bicliques, subgraphs of G, such that the bicliques are vertex disjoint with respect to a subset of vertices S, where S ∈ {V,L,R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique (MEB) problem is a special case of the mebp problem in which k=1. Several applications of the MEB problem have been studied and, in this paper, we describe applications of the mebp problem in metabolic networks and product bundling. In these applications the input graphs are very unbalanced (i.e., |R| is considerably greater than |L|), thus we consider carefully this property in our models. We introduce a new formulation for the meb problem and a branch-and-price scheme, using the classical branch rule by Ryan and Foster, for the mebp problem. Finally, we present computational experiments with instances that come from the described applications and also with randomly generated instances.

AB - A biclique is a complete bipartite graph. Given an (L,R)-bipartite graph G=(V,E) and a positive integer k, the maximum edge biclique packing (MEBP) problem consists in finding a set of at most k bicliques, subgraphs of G, such that the bicliques are vertex disjoint with respect to a subset of vertices S, where S ∈ {V,L,R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique (MEB) problem is a special case of the mebp problem in which k=1. Several applications of the MEB problem have been studied and, in this paper, we describe applications of the mebp problem in metabolic networks and product bundling. In these applications the input graphs are very unbalanced (i.e., |R| is considerably greater than |L|), thus we consider carefully this property in our models. We introduce a new formulation for the meb problem and a branch-and-price scheme, using the classical branch rule by Ryan and Foster, for the mebp problem. Finally, we present computational experiments with instances that come from the described applications and also with randomly generated instances.

KW - Branch-and-price

KW - Maximum edge biclique packing

KW - Metabolic networks

KW - Product bundling

UR - http://www.scopus.com/inward/record.url?scp=84893747996&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2011.09.019

DO - 10.1016/j.dam.2011.09.019

M3 - Article

AN - SCOPUS:84893747996

VL - 164

SP - 2

EP - 12

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - PART 1

ER -