کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419080 681741 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
چکیده انگلیسی

A biclique   is a complete bipartite graph. Given an (L,R)(L,R)-bipartite graph G=(V,E)G=(V,E) and a positive integer kk, the maximum edge biclique packing (mebp) problem consists in finding a set of at most kk bicliques, subgraphs of GG, such that the bicliques are vertex disjoint with respect to a subset of vertices SS, where S∈{V,L,R}S∈{V,L,R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique   (mebmeb) problem is a special case of the mebp  problem in which k=1k=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||R| is considerably greater than |L||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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 164, Part 1, 19 February 2014, Pages 2–12
نویسندگان
, , , ,