La idea de un MST de diámetro restringido es que mantenga todos los vértices conectados y dentro de una cierta distancia el uno del otro. Pero todos los papeles que he visto mantienen el requisito de que produzcas un árbol, cuando permitir ciclos podría ayudar a reducir el diámetro. ¿Alguien sabe de algún documento que explore esto? (Es difícil de buscar).
Por ejemplo, considere un gráfico completo con vértices dispuestos en un círculo en un plano (peso del borde = distancia euclidiana). El MST (por ejemplo, a través de Prim) seguirá el círculo, de modo que el diámetro del gráfico es aproximadamente la circunferencia del círculo . Al permitir que se conecte el borde final, podemos reducir a la mitad el diámetro, sin aumentar mucho el peso total.
Respuestas:
El subgrafo de diametro minimo es lo que deberia estar buscando. Es NP-Hard de calcular incluso en el caso de gráficos planos. Este documento ofrece una buena visión general.
fuente