Name
Abstract | ||
|---|---|---|
We are interested in the solution of the maximumk-balanced subgraph problem. Let G=(V,E,s) be a signed graph and k a positive scalar. A signed graph is k-balanced if V can be partitioned into at most k sets in such a way that positive edges are found only within the sets and negative edges go between sets. The maximum k-balanced subgraph problem is the problem of finding a subgraph of G that is k-balanced and maximum according to the number of vertices. This problem has applications in clustering problems appearing in collaborative vs conflicting environments. The particular case k=2 yields the problem of finding a maximum balanced subgraph in a signed graph and its exact solution has been addressed before in the literature. In this paper, we provide a representatives formulation for the general problem and present a partial description of the associated polytope, including the introduction of strengthening families of valid inequalities. A branch-and-cut algorithm is described for finding an optimal solution to the problem. An ILS metaheuristic is implemented for providing primal bounds for this exact method and a branching rule strategy is proposed for the representatives formulation. Computational experiments, carried out over a set of random instances and on a set of instances from an application, show the effectiveness of the valid inequalities and strategies adopted in this work. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.dam.2018.11.022 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Signed graph,Balanced graph,Graph partition,Integer programming,Social networks | Discrete mathematics,Combinatorics,Signed graph,Vertex (geometry),Branch and cut,Algorithm,Polytope,Integer programming,Cluster analysis,Graph partition,Mathematics,Metaheuristic | Journal |
Volume | ISSN | Citations |
261 | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 19 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rosa M. V. Figueiredo | 1 | 53 | 9.43 |
| Yuri Frota | 2 | 105 | 13.98 |
| M. Labbé | 3 | 36 | 3.98 |