| Attributs | Valeurs |
|---|
| type
| |
| Is Part Of
| |
| Subject
| |
| License
| |
| Title
| - A matheuristic approach for the maximum balanced subgraph of a signed graph
|
| Date
| |
| has manifestation of work
| |
| related by
| |
| Author
| |
| Abstract
| - A graph G = ( V, E) with its edges labeled in the set {+,-} is called a signed graph. It is balanced if its set of vertices V can be partitioned into two sets V1 and V2, such that all positive edges connect nodes within V1 or V2, and all negative edges connect nodes between V1 and V2. The maximum balanced subgraph problem (MBSP) for a signed graph is the problem of finding a balanced subgraph with the maximum number of vertices. In this work, we present the first polynomial integer linear programming formulation for this problem and a matheuristic to obtain good quality solutions in a short time. The results obtained for different sets of instances show the effectiveness of the matheuristic, optimally solving several instances and finding better results than the exact method in a much shorter computational time.
|
| article type
| |
| publisher identifier
| |
| Date Copyrighted
| |
| Rights
| - © The authors. Published by EDP Sciences, ROADEF, SMAI 2021
|
| Rights Holder
| - The authors. Published by EDP Sciences, ROADEF, SMAI 2021
|
| is part of this journal
| |
| is primary topic
of | |
