Sous-graphe planaire le plus lourd

Considérez le problème suivant.

Éléments fournis: un graphique complet avec des poids réels non négatifs sur les bords.

Tâche: trouver un sous-graphique planaire de poids maximum. ("Maximum" parmi tous les sous-graphiques planaires possibles.)

Remarque: Le sous-graphique de poids maximum sera une triangulation; si le graphique complet est sur sommets, il auraarêtes.$n$$m=3n-6$

Question: Quel est le meilleur algorithme disponible pour ce problème? Quelle est sa complexité temporelle?

$n-1$$3n-6$

$O(m^{3/2}n \log^6 n)$

[1] Calinescu, G., Fernandes, CG, Karloff, H. et Zelikovsky, A. (2003). Un nouvel algorithme d'approximation pour trouver des sous-graphes planaires lourds. Algorithmica, 36 (2), 179-205.