Published March 1, 2024 | Version v1
Publication Metadata-only

Innovative method to solve the minimum spanning tree problem: The Dhouib-Matrix-MSTP (DM-MSTP)

Creators

  • 1. University of Sfax

Description

The Minimum Spanning Tree problem aims to create a subset of a graph where all the vertices are connected with the minimum edge weights and with no cycle. In this field, an innovative method entitled Dhouib-Matrix-MSTP (DM-MSTP) is designed in this research work with a time complexity independently of the number of edges O(n*log(n)) where n is the number of vertices. DM-MSTP is a constructive algorithm based on a matrix navigation with two new lists (Min-Columns and MST-Path) in order to organize the steering flow. DM-MSTP is composed of four simple steps where the first and the fourth steps are repeated only once, whereas the second and third are reiterated (n-1). For more clarification, a step-by-step application of the proposed method is presented in details. Besides, the performance of DM-MSTP is proved through different examples from the literature including a graph with negative weighted edges and complete graphs from TSP-LIB. Moreover, with a simple modification (Min by Max) the DM-MSTP is tested on the Maximum (Largest) Spanning Tree Problem. Also, DM-MSTP is applied on eight case studies and compared to six methods developed in the literature. All these experimental results in the above different environments show that DM-MSTP can rapidly plan the shortest spanning tree with a stable performance and convivial representation of the optimal tree. Hence, DM-MSTP is developed under Python programming language using Matplotlib and Numpy standard libraries.

⚠️ This is an automatic machine translation with an accuracy of 90-95%

Translated Description (Arabic)

تهدف مشكلة شجرة الامتداد الدنيا إلى إنشاء مجموعة فرعية من الرسم البياني حيث ترتبط جميع الرؤوس بأوزان الحافة الدنيا وبدون دورة. في هذا المجال، تم تصميم طريقة مبتكرة بعنوان Dhouib - Matrix - MSTP (DM - MSTP) في هذا العمل البحثي مع تعقيد زمني بشكل مستقل عن عدد الحواف O(n*log(n)) حيث n هو عدد الرؤوس. DM - MSTP هي خوارزمية بناءة تعتمد على التنقل في المصفوفة مع قائمتين جديدتين (Min - Columns و MST - Path) من أجل تنظيم تدفق التوجيه. يتكون DM - MSTP من أربع خطوات بسيطة حيث يتم تكرار الخطوتين الأولى والرابعة مرة واحدة فقط، في حين يتم تكرار الخطوتين الثانية والثالثة (N -1). لمزيد من التوضيح، يتم تقديم تطبيق تدريجي للطريقة المقترحة بالتفصيل. إلى جانب ذلك، يتم إثبات أداء DM - MSTP من خلال أمثلة مختلفة من الأدبيات بما في ذلك رسم بياني مع حواف مرجحة سالبة ورسوم بيانية كاملة من TSP - LIB. علاوة على ذلك، مع تعديل بسيط (الحد الأدنى بواسطة الحد الأقصى)، يتم اختبار DM - MSTP على مشكلة شجرة الامتداد القصوى (الأكبر). أيضًا، يتم تطبيق DM - MSTP على ثماني دراسات حالة ومقارنة بست طرق تم تطويرها في الأدبيات. تُظهر كل هذه النتائج التجريبية في البيئات المختلفة المذكورة أعلاه أن DM - MSTP يمكنه التخطيط بسرعة لأقصر شجرة ممتدة مع أداء مستقر وتمثيل رائع للشجرة المثلى. وبالتالي، تم تطوير DM - MSTP تحت لغة برمجة بايثون باستخدام مكتبات Matplotlib و Numpy القياسية.

Translated Description (French)

Le problème de l'arbre couvrant minimum vise à créer un sous-ensemble d'un graphique où tous les sommets sont connectés avec les poids d'arête minimum et sans cycle. Dans ce domaine, une méthode innovante intitulée Dhouib-Matrix-MSTP (DM-MSTP) est conçue dans ce travail de recherche avec une complexité temporelle indépendante du nombre d'arêtes O(n*log(n)) où n est le nombre de sommets. DM-MSTP est un algorithme constructif basé sur une navigation matricielle avec deux nouvelles listes (Min-Columns et MST-Path) afin d'organiser le flux de pilotage. Le DM-MSTP est composé de quatre étapes simples où la première et la quatrième étapes ne sont répétées qu'une seule fois, tandis que la deuxième et la troisième sont réitérées (n-1). Pour plus de clarté, une application étape par étape du procédé proposé est présentée en détail. En outre, la performance de DM-MSTP est prouvée à travers différents exemples de la littérature, y compris un graphique avec des arêtes pondérées négatives et des graphiques complets de TSP-LIB. De plus, avec une simple modification (Min par Max), le DM-MSTP est testé sur le problème de l'arbre maximal (le plus grand). De plus, le DM-MSTP est appliqué sur huit études de cas et comparé à six méthodes développées dans la littérature. Tous ces résultats expérimentaux dans les différents environnements ci-dessus montrent que le DM-MSTP peut planifier rapidement l'arbre couvrant le plus court avec une performance stable et une représentation conviviale de l'arbre optimal. Par conséquent, DM-MSTP est développé sous le langage de programmation Python en utilisant les bibliothèques standard Matplotlib et Numpy.

Translated Description (Spanish)

El problema del árbol de expansión mínimo tiene como objetivo crear un subconjunto de un gráfico donde todos los vértices estén conectados con los pesos de borde mínimos y sin ciclo. En este campo, se diseña un método innovador titulado Dhouib-Matrix-MSTP (DM-MSTP) en este trabajo de investigación con una complejidad temporal independiente del número de aristas O(n*log(n)) donde n es el número de vértices. DM-MSTP es un algoritmo constructivo basado en una navegación matricial con dos nuevas listas (Min-Columns y MST-Path) para organizar el flujo de dirección. DM-MSTP se compone de cuatro pasos simples donde el primer y el cuarto paso se repiten solo una vez, mientras que el segundo y el tercero se reiteran (n-1). Para mayor aclaración, se presenta en detalle una aplicación paso a paso del método propuesto. Además, el rendimiento de DM-MSTP se demuestra a través de diferentes ejemplos de la literatura, incluido un gráfico con bordes ponderados negativos y gráficos completos de TSP-LIB. Además, con una simple modificación (Min por Max), el DM-MSTP se prueba en el problema del árbol de expansión máximo (más grande). Además, DM-MSTP se aplica en ocho estudios de casos y se compara con seis métodos desarrollados en la literatura. Todos estos resultados experimentales en los diferentes entornos anteriores muestran que DM-MSTP puede planificar rápidamente el árbol de expansión más corto con un rendimiento estable y una representación agradable del árbol óptimo. Por lo tanto, DM-MSTP se desarrolla bajo el lenguaje de programación Python utilizando las bibliotecas estándar Matplotlib y Numpy.

Additional details

Additional titles

Translated title (Arabic)
طريقة مبتكرة لحل مشكلة شجرة الامتداد الدنيا: دويب- مصفوفة- MSTP (DM - MSTP)
Translated title (French)
Méthode innovante pour résoudre le problème de l'arbre couvrant minimum : Le Dhouib-Matrix-MSTP (DM-MSTP)
Translated title (Spanish)
Método innovador para resolver el problema del árbol de expansión mínimo: el Dhouib-Matrix-MSTP (DM-MSTP)

Identifiers

Other
https://openalex.org/W4389419870
DOI
10.1016/j.rico.2023.100359

Is supplement to
https://openalex.org/W2099915933 (Other)
https://openalex.org/W3116169590 (Other)
https://openalex.org/W1703428550 (Other)
https://openalex.org/W4380840098 (Other)
https://openalex.org/W2044443696 (Other)
https://openalex.org/W2503538928 (Other)
https://openalex.org/W3101281637 (Other)
https://openalex.org/W2390742649 (Other)
https://openalex.org/W1561849181 (Other)
https://openalex.org/W2418231958 (Other)

GreSIS Basics Section

Is Global South Knowledge
Yes
Country
Tunisia

References

  • https://openalex.org/W1965680834
  • https://openalex.org/W2017927472
  • https://openalex.org/W2071346873
  • https://openalex.org/W2088814889
  • https://openalex.org/W2123757175
  • https://openalex.org/W2180968341
  • https://openalex.org/W2220479098
  • https://openalex.org/W2249259319
  • https://openalex.org/W2300051232
  • https://openalex.org/W2509969081
  • https://openalex.org/W2566560803
  • https://openalex.org/W2745422985
  • https://openalex.org/W2967092405
  • https://openalex.org/W3008588639
  • https://openalex.org/W3024422466
  • https://openalex.org/W3103514293
  • https://openalex.org/W3204258093
  • https://openalex.org/W3210307938
  • https://openalex.org/W4200360130
  • https://openalex.org/W4210682474
  • https://openalex.org/W4211263731
  • https://openalex.org/W4214893413
  • https://openalex.org/W4285167802
  • https://openalex.org/W4285358075
  • https://openalex.org/W4288041784
  • https://openalex.org/W4300593403
  • https://openalex.org/W4302024718
  • https://openalex.org/W4309149619
  • https://openalex.org/W4312191925
  • https://openalex.org/W4313211014
  • https://openalex.org/W4313213873
  • https://openalex.org/W4313214593
  • https://openalex.org/W4313303087
  • https://openalex.org/W4317473380
  • https://openalex.org/W4321455657
  • https://openalex.org/W4323058610
  • https://openalex.org/W4378071241
  • https://openalex.org/W4384563777
  • https://openalex.org/W4386573823
  • https://openalex.org/W4387271725