Diametro Restringido Gráfico de expansión mínima

8

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.

Dijkstra
fuente
1
No está muy claro lo que estás pidiendo. ¿Cuáles son sus limitaciones y cuál es su función objetivo? Mi conjetura es que desea restringir el número de bordes y minimizar el diámetro. ¿O viceversa?
zotachidil
3
Bueno, es comprensible que todos los papeles en MST de diámetro limitado cumplan con el requisito de árbol ...
Tsuyoshi Ito

Respuestas:

12

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.

Nicholas Mancuso
fuente