HomeIssuesFPT-algorithms on graphs of limited treewidth

FPT-algorithms on graphs of limited treewidth | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 2(16).

A method for designing FPT-algorithms by means of dynamic programming based on thetree decomposition is investigated. Some problems limiting the application of this methodin practice are pointed. The problem of memory is solved by using a binary tree decompositionof the separator, which reduces the theoretical and the actual size of the dynamicprogramming tables. The technique of tables in the language of relational algebra is described.
Download file
Counter downloads: 71
  • Title FPT-algorithms on graphs of limited treewidth
  • Headline FPT-algorithms on graphs of limited treewidth
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(16)
  • Date:
  • DOI
Keywords
dynamic programming, tree decomposition, graph algorithms, динамическое программирование, дерево декомпозиции, алгоритмы на графах
Authors
References
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-algorithms on graphs of limited treewidth | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 2(16).
FPT-algorithms on graphs of limited treewidth | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 2(16).
Download full-text version
Counter downloads: 214
Download file