Рассмотрим следующую проблему.
Дано: Полный граф с действительными неотрицательными весами по ребрам.
Задача: Найти планарный подграф максимального веса. («Максимум» среди всех возможных плоских подграфов.)
Примечание: подграф максимального веса будет триангуляцией; если полный граф находится на вершинах, он будет иметь m = 3 n - 6 ребер.
Вопрос: Каков наилучший доступный алгоритм для этой проблемы? Какова его временная сложность?