Subgráfico plano mais pesado

Considere o seguinte problema.

Dado: Um gráfico completo com pesos reais não negativos nas bordas.

Tarefa: Encontre um subgráfico plano de peso máximo. ("Máximo" entre todos os subgráficos planares possíveis.)

Nota: O subgrafo de peso máximo será uma triangulação; se o gráfico completo estiver em vértices, ele terá m = 3 n - 6 arestas.$n$$m=3n-6$

Pergunta: Qual é o melhor algoritmo disponível para esse problema? Qual é a complexidade do tempo?

$n-1$$3n-6$

Para gráficos completos cujos pesos das arestas obedecem à desigualdade do triângulo, a taxa de desempenho do algoritmo em [1] é de pelo menos 3/8. Acho que o algoritmo está bastante envolvido e pode ser executado em $O(m^{3/2}n \log^6 n)$

[1] Calinescu, G., Fernandes, CG, Karloff, H. e Zelikovsky, A. (2003). Um novo algoritmo de aproximação para encontrar subgráficos planares pesados. Algoritmica, 36 (2), 179-205.