Цветовое кодирование: различия между версиями

Изначальная цель заключалась в разработке эффективных алгоритмов для нахождения простых путей и циклов в графах. Однако впоследствии оказалось, что потенциальная область применения метода цветового кодирования значительно шире. Линейные временные границы (т. е. <math>2^{O(k)} \cdot |E|</math> для ориентированных графов и <math>2^{O(k)} \cdot |V|</math> - для неориентированных) для простых путей фактически применимы к любому ''лесу'' с ''k'' вершинами. Граница <math>2^{O(k)} \cdot |V|^{\omega}</math> для простых циклов фактически применима к любому ''серийно-параллельному'' графу с k вершинами. В общем случае, если граф G = (V, E) сдержит подграф, изоморфный графу <math>H = (V_H, E_H)</math>, ''древесная ширина'' которого не превышает t, то такой подграф можно найти за ожидаемое время <math>2^{O(k)} \cdot |V|^{t + 1}</math>, где <math>k = |V_H|</math>. Это улучшает результаты алгоритма Плена и Войта [14], время выполнения которого составляет <math>k^{O(k)} \cdot |V|^{t + 1}</math>. В качестве специального случая можно сделать вывод, что задача LOG PATH входит в P. Таким образом, на гипотезу Пападимитриу и Яннакакиса [13] можно дать положительный ответ. От экспоненциальной зависимости от k в вышеприведенных границах, вероятно, избавиться не получится, поскольку задача является NP-полной при наличии k во входных данных.

* [[Схемы аппроксимации для задач с планарными графами]]