Аннотация:
Исследован специальный метод конструирования FPT-алгоритмов – метод динамического программирования на основе дерева декомпозиции. Выявлены проблемы, ограничивающие применение этого метода на практике. Предложено проблему памяти решать с помощью бинарного сепараторного дерева декомпозиции, снижающего теоретические и реальные размеры таблиц динамического программирования. Табличная техника описана на языке реляционной алгебры.
Ключевые слова:алгоритмы на графах, дерево декомпозиции, динамическое программирование.
Полный текст:
PDF файл (1344 kB)