Interval vertex-colorings of cactus graphs with restrictions on vertices

Интервальная раскраска вершин графа $G$ – это раскраска вершин графа такими интервалами целых чисел, что интервалы любых двух соседних вершин не пересекаются. В работе рассматривается случай, когда для каждой вершины $v$ кактуса заданы длина $l (v)$ и множество цветов $S (v)$, из которого должны быть выбраны цвета. Требуется найти такую интервальную раскраску $\gamma$ вершин кактуса, при которой для каждой вершины $v$ ограничения соблюдаются, т.е. $|\gamma(v)|=l(v), \gamma(v) \subseteq S(v)$. Представлен псевдополиномиальный алгоритм решения задачи для кактусов.