Точные алгоритмы построения доминирующего множества: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 83: | Строка 83: | ||
Простые алгоритмы ветвления и редукции в наихудшем случае, подобные алгоритмам нахождения минимального доминирующего множества или минимального покрытия множества, также пока неизвестны. В случае алгоритма нахождения минимального доминирующего множества с использованием полиномиального объема памяти разрыв между верхней границей O( | Простые алгоритмы ветвления и редукции в наихудшем случае, подобные алгоритмам нахождения минимального доминирующего множества или минимального покрытия множества, также пока неизвестны. В случае алгоритма нахождения минимального доминирующего множества с использованием полиномиального объема памяти разрыв между верхней границей <math>O(2^{0.610n}) \; </math> и нижней границей <math>\Omega (2^{n/3}) \; </math> слишком велик. Подобная же ситуация наблюдается и для других алгоритмов ветвления и редукции. Следовательно, существует значительная потребность в новых и более мощных инструментах анализа алгоритмов ветвления и редукции в наихудшем случае. | ||
== См. также == | == См. также == | ||