Параметризованные алгоритмы графического представления графов: различия между версиями

Для задач, для которых не предполагается существования полиномиальных алгоритмов, очень желательно найти точные алгоритмы с экспоненциальным временем исполнения.

Возможный вариант исполнения улучшенного алгоритма поиска по дереву приведен на рис. 2, а его (оптимальный) результат – на рис. 3.

1. Изменение цели оптимизации: минимизация количества дуг, участвующих в пересечениях – одноуровневая планаризация. Как было отмечено в [7, 10], из теоремы 2 практически непосредственно следует идея алгоритма решения этой задачи с временем исполнения <math>O^*(3^k) \;</math>, которое впоследствии было улучшено в [10] до <math>O^*(2^k) \;</math>.

Как и для всех алгоритмов с экспоненциальным временем исполнения, оказывается непросто улучшить это время или доказать определенную нижнюю границу времени исполнения при наличии разумных теоретико-сложностных предположений. Заметим, что негласные предположения, лежащие в основе подхода параметризованных алгоритмов, в данном сценарии полностью удовлетворяются: к примеру, графическое представление с большим количеством пересечений будет неприемлемым (если такая ситуация встретится на практике, придется прибегнуть к другому способу представления информации); таким образом, можно обоснованно предполагать, что параметр действительно окажется малым.