Edge cover by connected bipartite subgraphs |
| |
Authors: | Leo Liberti Laurent Alfandari Marie-Christine Plateau |
| |
Institution: | (3) Information Sci. Res. AT&T Labs Res., Florham Park, NJ 07932, USA;(4) Dept. Computer Sci. Catholic Univ. Rio de Janeiro, Rio de Janeiro, RJ, 22453-900, Brazil |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|