Перевод названия: 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)
- Список ВАК
Информация о публикациях загружается с сайта службы поддержки публикационной активности СФУ. Сообщите, если заметили неточности.