Перевод названия: FPT-algorithms on graphs of limited treewidth
Тип публикации: статья из журнала
Год издания: 2012
Ключевые слова: Graph algorithms, Tree decomposition, dynamic programming, алгоритмы на графах, дерево декомпозиции, динамическое программирование
Аннотация: Исследован специальный метод конструирования FPT-алгоритмов - метод динамического программирования на основе дерева декомпозиции. Выявлены проблемы, ограничивающие применение этого метода на практике. Предложено проблему памяти решать с помощью бинарного сепараторного дерева декомпозиции, снижающего теоретические и реальные размерыПоказать полностьютаблиц динамического программирования. Табличная техника описана на языке реляционной алгебры. A method for designing FPT-algorithms by means of dynamic programming based on the tree decomposition is investigated. Some problems limiting the application of this method in practice are pointed. The problem of memory is solved by using a binary tree decomposition of the separator, which reduces the theoretical and the actual size of the dynamic programming tables. The technique of tables in the language of relational algebra is described.
Журнал: Прикладная дискретная математика
Выпуск журнала: № 2
Номера страниц: 65-78
ISSN журнала: 20710410
Место издания: Томск
Издатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Национальный исследовательский Томский государственный университет