Return to results
Journal articles (2011), Annals of Operations Research, 188 (1), pp. 307-329

Edge Cover by Connected Bipartite Subgraphs


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 IP 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 IP formulation for the variant. Link to the article

LIBERTI, L., ALFANDARI, L. and PLATEAU, M.C. (2011). Edge Cover by Connected Bipartite Subgraphs. Annals of Operations Research, 188(1), pp. 307-329.

Keywords : #Local-Search, #Bipartite-Graph, #Vertex-Cover, #Constructive-Heuristic, #Edge-Cover