Алгоритмы решения задач на графах с ограниченной путевой шириной

Приведена эффективная по используемой памяти общая схема решения задач для классов графов с ограниченной путевой шириной. Даны алгоритмы для решения задач: о покрытии графа цепями ограниченного веса и о гамильтоновом цикле наименьшего веса, имеющие временную сложность $O(n\log n)$ и использующие $O(1)$ дополнительной памяти, для графов с ограниченной путевой шириной. Представлен аналогичный алгоритм для решения задачи 3-ВЫПОЛНИМОСТЬ, у которой входом является формула и ее граф взаимовлияния, заданный вместе с путевой декомпозицией, ширина которой не превосходит константы.