Gráfico de abrangência mínima de diâmetro restrito

8

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.

Dijkstra
fonte
1
Não está muito claro o que você está pedindo. Quais são as suas restrições e qual é a sua função objetiva? Meu palpite é que você deseja restringir o número de arestas e minimizar o diâmetro. Ou vice-versa?
Zotachidil
3
Bem, é compreensível que todos os papéis em MST com diâmetro restrito cumpram os requisitos de árvore….
Tsuyoshi Ito

Respostas:

12

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.

Nicholas Mancuso
fonte