Edge cover by connected bipartite subgraphs

Edge cover by connected bipartite subgraphs

0.00 Avg rating0 Votes
Article ID: iaor20117904
Volume: 188
Issue: 1
Start Page Number: 307
End Page Number: 329
Publication Date: Aug 2011
Journal: Annals of Operations Research
Authors: , ,
Keywords: programming: integer
Abstract:

We consider the problem of covering the edge set of an unweighted, undirected graph with the minimum number of connected bipartite subgraphs (where the subgraphs are not necessarily bicliques). We show that this is an NP‐hard problem, provide lower bounds through an integer programming formulation, propose several constructive heuristics and a local search, and discuss computational results. Finally, we consider a constrained variant of the problem which we show to be NP‐hard, and provide an integer programming formulation for the variant.

Reviews

Required fields are marked *. Your email address will not be published.