Быстрая минимальная триангуляция: различия между версиями

Приведенный алгоритм позволяет найти минимальную триангуляцию за время <math>O((n^2 + n^{ \alpha }) log \; n)</math>, где <math>O(n^{ \alpha }) \; </math> – время, необходимое для проведения бинарного матричного умножения <math>n \times n \; </math>. В результате любое улучшение алгоритма бинарного матричного умножения позволит повысить скорость алгоритма нахождения минимальной триангуляции. Интересный вопрос заключается в том, верно ли обратное: существует ли алгоритм бинарного матричного умножения с временем <math>O((n^2 + n^{ \beta })f(n)) \; </math>, где <math>O(n^{ \beta }) \; </math> – время, необходимое для нахождения минимальной триангуляции, и <math>f(n) = o(n^{ \alpha -2}) \; </math> или по меньшей мере <math>f(n) = O(n) \; </math>. Более простой и релевантный вопрос был ранее задан в [8]: сложнее ли вычислить минимальную триангуляцию, чем определить, содержит ли граф хотя бы один треугольник? Более алгоритмический вопрос выглядит следующим образом: существует ли алгоритм нахождения минимальной триангуляции за время <math>O(n^2 + n^{ \alpha }) \; </math>.