Сибирский федеральный университет

Перевод названия: 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

Место издания: Томск

Издатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Национальный исследовательский Томский государственный университет

• Быкова Валентина Владимировна (Сибирский федеральный университет)

• Ядро РИНЦ (eLIBRARY.RU)
• Список ВАК