Diámetro (teoría de grafos)

El diámetro de un grafo se puede calcular utilizando un algoritmo de camino más corto para calcular los caminos más cortos entre todos los pares de vértices y luego tomando el máximo de las distancias que calcula. Por ejemplo, en un grafo con pesos de arista positivos, esto se puede hacer utilizando repetidamente el algoritmo de Dijkstra , una vez para cada posible vértice inicial. En un grafo con${\displaystyle n}$vértices y${\displaystyle m}$bordes, esto lleva tiempo${\displaystyle O(mn+n^{2}\log n)}$El cálculo de los caminos más cortos entre todos los pares de nodos es el método más rápido conocido para calcular con exactitud el diámetro de un grafo ponderado. ^{[ 4 ]}

En un grafo no ponderado, el algoritmo de Dijkstra puede reemplazarse por una búsqueda en anchura , lo que da como resultado un tiempo${\displaystyle O(mn)}$. Alternativamente, el diámetro puede calcularse utilizando un algoritmo basado en la multiplicación rápida de matrices , en un tiempo proporcional al tiempo de multiplicación.${\displaystyle n\times n}$matrices, aproximadamente${\displaystyle O(n^{2.37})}$utilizando algoritmos conocidos de multiplicación de matrices. ^{[ 5 ]} Para grafos dispersos, con pocas aristas, la búsqueda en anchura repetida es más rápida que la multiplicación de matrices. Suponiendo la hipótesis de tiempo exponencial fuerte , la búsqueda en anchura repetida es casi óptima: esta hipótesis implica que ningún algoritmo puede alcanzar tiempo${\displaystyle O(m^{2-\varepsilon })}$para cualquier${\displaystyle \varepsilon >0}$. ^{[ 4 ]}

Es posible aproximar el diámetro de un gráfico ponderado con una relación de aproximación de 3/2, en el tiempo${\displaystyle {\tilde {O}}(\min(m^{3/2},mn^{2/3})}$, donde el${\displaystyle {\tilde {O}}}$La notación oculta factores logarítmicos en el límite de tiempo. ^{[ 6 ]} Bajo la hipótesis de tiempo exponencial fuerte, no es posible una aproximación sustancialmente más precisa, sustancialmente más rápida que todos los caminos más cortos entre pares. ^{[ 4 ]}

El diámetro se puede calcular en tiempo lineal para grafos de intervalos [ ^{7 ]} y en tiempo casi lineal para grafos de ancho de árbol acotado ^{[ 8 ]} . En grafos medianos , el diámetro se puede encontrar en el límite de tiempo subcuadrático ^.${\displaystyle {\tilde {O}}(n^{1.6456})}$. ^{[ 9 ]} En cualquier clase de grafos cerrados bajo menores de grafos , como los grafos planares , es posible calcular el diámetro en tiempo subcuadrático, con un exponente que depende de la familia de grafos. ^{[ 10 ]}