Самый тяжелый плоский подграф

9

Рассмотрим следующую проблему.

Дано: Полный граф с действительными неотрицательными весами по ребрам.

Задача: Найти планарный подграф максимального веса. («Максимум» среди всех возможных плоских подграфов.)

Примечание: подграф максимального веса будет триангуляцией; если полный граф находится на вершинах, он будет иметь m = 3 n - 6 ребер.Nмзнак равно3N-6

Вопрос: Каков наилучший доступный алгоритм для этой проблемы? Какова его временная сложность?

Елена Ф.
источник

Ответы: