Algoritmos de aproximación del diámetro de grafos dirigidos y no dirigidos

Abstract

En teoría de grafos, el diámetro de un grafo hace referencia a la mayor distancia posible entre dos de sus vértices, donde la distancia se define como la longitud del camino más corto entre esos dos vértices. El coste temporal de calcular el diámetro de un grafo en el caso peor sin recurrir a la multiplicación de matrices es cubico con respecto al número de vértices del grafo. Por ello, en las últimas décadas, se han propuesto algoritmos de aproximación del diámetro de grafos dirigidos y no dirigidos. En esta memoria se estudia en detalle el diseño de uno de estos algoritmos, con factor de aproximación 1.5-aproximado y coste temporal subcúbico en el caso peor. Se explica también su versión probabilística, que reduce el coste temporal sin perder calidad en la aproximación. Finalmente se recogen los resultados obtenidos con la implementación de estos algoritmos y otro más sencillo con factor de aproximación 2-aproximado, y se evalúan y comparan entre ellos en cuanto a su capacidad de aproximación del diámetro y en cuanto a su coste temporal empírico.

In graph theory, the diameter of a graph refers to the biggest possible distance between two of its vertices, where the distance is defined as the length of the shortest path between these two vertices. The time cost of computing the diameter of a graph in the worst case without resorting to matrix multiplication is cubic with respect to the number of vertices in the graph. Because of that, in the last decades, some approximation algorithms of the diameter in directed and undirected graphs have been proposed. In this memory is studied in detail the design of one of these algorithms, with a ratio 1.5 approximation and subcubic time cost in the worst case. Its probabilistic version is also explained, which reduces the time cost without losing quality in the approximation. Finally, the results obtained with the implementation of these algorithms and another simpler one with approximation factor 2-approximate are collected, and they are evaluated and compared among them in terms of its ability to approximate the diameter and in terms of its empirical time cost.