Subgrafo plano mas pesado

9

Considere el siguiente problema.

Dado: Un gráfico completo con pesos reales no negativos en los bordes.

Tarea: Encuentre un subgrafo plano de peso máximo. ("Máximo" entre todos los subgrafos planos posibles.)

Nota: El subgrafo de peso máximo será una triangulación; Si el gráfico completo está en vértices, tendrá m = 3 n - 6 aristas.nm=3n6

Pregunta: ¿Cuál es el mejor algoritmo disponible para este problema? ¿Cuál es su complejidad temporal?

Helen F.
fuente

Respuestas: