Árbol de expansión con coste mínimo de enrutamiento

En informática , el árbol de expansión de costo de enrutamiento mínimo de un grafo ponderado es un árbol de expansión que minimiza la suma de las distancias por pares entre vértices en el árbol. También se le llama árbol de expansión de distancia óptima , árbol de expansión de longitud de camino total más corta , árbol de expansión de distancia total mínima o árbol de expansión de distancia promedio mínima . En un grafo no ponderado, este es el árbol de expansión de índice de Wiener mínimo . ^{[ 1 ]} Hu (1974) escribe que el problema de construir estos árboles fue propuesto por Francesco Maffioli. ^{[ 2 ]}

Su construcción es NP-difícil , incluso para grafos no ponderados. ^{[ 3 ] [ 4 ]} Sin embargo, tiene un esquema de aproximación de tiempo polinomial . La aproximación funciona eligiendo un número${\displaystyle k}$que depende de la relación de aproximación pero no del número de vértices del grafo de entrada, y buscando entre todos los árboles con${\displaystyle k}$nodos internos. ^{[ 5 ]}

El árbol de expansión de costo de enrutamiento mínimo de un grafo de intervalos no ponderado se puede construir en tiempo lineal. ^{[ 6 ]} También se conoce un algoritmo de tiempo polinomial para grafos hereditarios de distancia , ponderados de manera que las distancias ponderadas sean hereditarias. ^{[ 7 ]}

Diversos estudios parten de la base de que diferentes personas pueden tener diferentes preferencias sobre las aristas del grafo, y el objetivo es encontrar un árbol de expansión que sea el mejor desde el punto de vista "social".

• Darmann, Klamler y Pferschy presentan un algoritmo voraz que encuentra dicho árbol de expansión. ^{[ 8 ]}

• Escoffier, Gourvès y Monnot estudian el problema bajo la regla igualitaria : maximizar la utilidad mínima de un agente. ^{[ 9 ]}
• Galand, Perny y Spanjaard estudian el problema bajo el criterio de minimizar la integral de Choquet . ^{[ 10 ]}

• Diseño óptimo de redes : el problema de encontrar un conjunto generador (no necesariamente un árbol) que minimice la suma de las longitudes de los caminos más cortos.