Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10346558 | Computers & Operations Research | 2011 | 10 Pages |
Abstract
We study the problem of detecting a maximum embedded network submatrix in a {â1,0,+1}-matrix. Our aim is to solve the problem to optimality. We introduce a 0-1 integer linear programming formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an optimal solution to the problem. Some computational experiments are carried out over a set of instances available in the literature as well as over a set of random instances.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Rosa M.V. Figueiredo, Martine Labbé, Cid C. de Souza,