ГлавнаяАрхивFPT-алгоритмы на графах ограниченной древовидной ширины

FPT-алгоритмы на графах ограниченной древовидной ширины | Прикладная дискретная математика. 2012. № 2(16).

Исследован специальный метод конструирования FPT-алгоритмов - метод динамического программирования на основе дерева декомпозиции. Выявлены проблемы, ограничивающие применение этого метода на практике. Предложено проблему памяти решать с помощью бинарного сепараторного дерева декомпозиции, снижающего теоретические и реальные размеры таблиц динамического программирования. Табличная техника описана на языке реляционной алгебры.
  • Title FPT-алгоритмы на графах ограниченной древовидной ширины
  • Headline FPT-алгоритмы на графах ограниченной древовидной ширины
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(16)
  • Date:
  • DOI
Ключевые слова
dynamic programming, tree decomposition, graph algorithms, динамическое программирование, дерево декомпозиции, алгоритмы на графах
Авторы
Ссылки
Kloks T. Treewidth. Computations and Approximations. Springer Verlag. LNCS. 1994. V. 842.
Bodlaender H. L. and Fomin F. V. Tree decompositions with small cost // Discr. Appl. Math. 2005. V. 145(2). P. 143-154.
Aspvall B., Proskurowski A., and Telle J. A. Memory requirements for table computations in partial k-tree algorithms // Algorithmica. 2000. V. 27(3). P. 382-394.
Быкова В. В. Математические методы анализа рекурсивных алгоритмов // Журнал СФУ. Математика и физика. 2008. № 1(3). С. 236-246.
Bodlaender H. L. and Kloks T. Efficient and constructive algorithms for the pathwidth and treewidth of graphs // J. Algorithms. 1996. V.21. P. 358-402.
Courcelle B. The monadic second-order logic of graphs. III. Tree decompositions, minors and complexity issues // RAIRO Inform. Theor. Appl. 1992. V.26(3). P. 257-286.
Мейер Д. Теория реляционных баз данных. М.: Мир, 1987.
Быкова В. В. Вычислительные аспекты древовидной ширины графа // Прикладная дискретная математика. 2011. №3(13). С. 65-79.
Компьютер и задачи выбора. М.: Наука, 1989.
Bodlaender H. L. Treewidth: Algorithmic techniques and results // LNCS. 1997. V. 1295. P. 19-36.
Быкова В. В. FPT-алгоритмы и их классификация на основе эластичности // Прикладная дискретная математика. 2011. №2(12). С. 40-48.
Downey R. and Fellows M. Parameterized complexity. New York: Springer Verlag, 1999.
FPT-алгоритмы на графах ограниченной древовидной ширины | Прикладная дискретная математика. 2012. № 2(16).
FPT-алгоритмы на графах ограниченной древовидной ширины | Прикладная дискретная математика. 2012. № 2(16).
Полнотекстовая версия