Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
Acuna
V
author
Ferreira
C
E
author
Freire
A
S
author
Moreno
E
author
2014
English
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 (num') 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 E {V, L, R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique (mEs) 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., IRI is considerably greater than ILI), 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. (C) 2011 Elsevier B.V. All rights reserved.
Maximum edge biclique packing
Branch-and-price
Metabolic networks
Product bundling
WOS:000332427400002
exported from refbase (http://ficpubs.uai.cl/show.php?record=361), last updated on Thu, 17 Apr 2014 06:23:14 -0400
text
http://ficpubs.uai.cl/files/163_Acuna_etal2011.pdf
10.1016/j.dam.2011.09.019
Acuna_etal2014
Discrete Applied Mathematics
Discret Appl. Math.
2014
Elsevier Science Bv
continuing
periodical
academic journal
164
2
12
0166-218x