Published September 1, 2021
| Version v1
Publication
Open
A matheuristic approach for the maximum balanced subgraph of a signed graph
- 1. Universidade Federal Fluminense
Description
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 V 1 and V 2 , such that all positive edges connect nodes within V 1 or V 2 , and all negative edges connect nodes between V 1 and V 2 . 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.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
يسمى الرسم البياني G = ( V، E ) بحوافه المسماة في المجموعة {+،-} رسمًا بيانيًا موقّعًا. يتم موازنتها إذا كان من الممكن تقسيم مجموعة قممها V إلى مجموعتين V 1 و V 2 ، بحيث تربط جميع الحواف الموجبة العقد داخل V 1 أو V 2 ، وتربط جميع الحواف السالبة العقد بين V 1 و V 2 . الحد الأقصى لمسألة الرسم البياني الفرعي المتوازن (MBSP) للرسم البياني الموقّع هي مشكلة إيجاد رسم بياني فرعي متوازن مع الحد الأقصى لعدد الرؤوس. في هذا العمل، نقدم أول صياغة برمجة خطية لعدد صحيح متعدد الحدود لهذه المشكلة ورياضية للحصول على حلول ذات نوعية جيدة في وقت قصير. تُظهر النتائج التي تم الحصول عليها لمجموعات مختلفة من الحالات فعالية الرياضيات، وحل العديد من الحالات على النحو الأمثل وإيجاد نتائج أفضل من الطريقة الدقيقة في وقت حسابي أقصر بكثير.Translated Description (French)
Un graphe G = ( V, E ) avec ses bords étiquetés dans l'ensemble {+,-} est appelé graphe signé. Il est équilibré si son ensemble de sommets V peut être divisé en deux ensembles V 1 et V 2 , de sorte que tous les bords positifs connectent des nœuds dans V 1 ou V 2 , et tous les bords négatifs connectent des nœuds entre V 1 et V 2 . Le problème du sous-graphe équilibré maximum (MBSP) pour un graphe signé est le problème de trouver un sous-graphe équilibré avec le nombre maximum de sommets. Dans ce travail, nous présentons la première formulation de programmation linéaire d'entiers polynomiaux pour ce problème et un matheuristique pour obtenir des solutions de bonne qualité en peu de temps. Les résultats obtenus pour différents ensembles d'instances montrent l'efficacité de la matheuristique, en résolvant de manière optimale plusieurs instances et en trouvant de meilleurs résultats que la méthode exacte dans un temps de calcul beaucoup plus court.Translated Description (Spanish)
Un gráfico G = ( V, E ) con sus aristas etiquetadas en el conjunto {+,-} se denomina gráfico con signo. Se equilibra si su conjunto de vértices V se puede dividir en dos conjuntos V 1 y V 2 , de modo que todos los bordes positivos conecten nodos dentro de V 1 o V 2 , y todos los bordes negativos conecten nodos entre V 1 y V 2 . El problema del subgrafo equilibrado máximo (MBSP) para un gráfico con signo es el problema de encontrar un subgrafo equilibrado con el número máximo de vértices. En este trabajo, presentamos la primera formulación polinómica de programación lineal entera para este problema y una matemática para obtener soluciones de buena calidad en poco tiempo. Los resultados obtenidos para diferentes conjuntos de instancias muestran la efectividad de la matemática, resolviendo de manera óptima varias instancias y encontrando mejores resultados que el método exacto en un tiempo computacional mucho más corto.Files
ro210030.pdf.pdf
Files
(24 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:7624dcbc096921e31a1da610e19a546e
|
24 Bytes | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- نهج رياضي للرسم البياني الفرعي المتوازن الأقصى للرسم البياني الموقع
- Translated title (French)
- Une approche matheuristique pour le sous-graphe équilibré maximal d'un graphe signé
- Translated title (Spanish)
- Un enfoque matemático para el subgrafo máximo equilibrado de un gráfico con signo
Identifiers
- Other
- https://openalex.org/W3200437044
- DOI
- 10.1051/ro/2021150
References
- https://openalex.org/W1499307573
- https://openalex.org/W1984619586
- https://openalex.org/W1994941014
- https://openalex.org/W2004147977
- https://openalex.org/W2008881234
- https://openalex.org/W2030737920
- https://openalex.org/W2082844239
- https://openalex.org/W2114051435
- https://openalex.org/W2120470208
- https://openalex.org/W2122873982
- https://openalex.org/W2292659810
- https://openalex.org/W2804679606
- https://openalex.org/W2891976039
- https://openalex.org/W3024588835
- https://openalex.org/W4232688408
- https://openalex.org/W4299572240