A idéia de um MST com diâmetro restrito é que você mantenha todos os vértices conectados e a uma certa distância um do outro. Mas todos os papéis que eu vi cumprem a exigência de que você produza uma árvore, ao permitir ciclos pode ajudar a reduzir o diâmetro. Alguém conhece algum artigo que explora isso? (É difícil procurar.)
Por exemplo, considere um gráfico completo com vértices dispostos em círculo em um plano (peso da aresta = distância euclidiana). O MST (por exemplo, via Prim's) seguirá o círculo, de modo que o diâmetro do gráfico seja aproximadamente a circunferência do círculo . Ao permitir que a aresta final seja conectada, podemos reduzir pela metade o diâmetro, sem aumentar muito o peso total.
Respostas:
O subgráfico de diâmetro mínimo é o que você deve procurar. É NP-Difícil calcular mesmo no caso de gráficos planares. Este artigo fornece uma boa visão geral.
fonte