Geodesic
Methods for designing FPT-algorithms on graphs of limited treewidth
Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 102-104 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{PDMA_2012_5_a54,
     author = {V. V. Bykova},
     title = {Methods for designing {FPT-algorithms} on graphs of limited treewidth},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {102--104},
     year = {2012},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2012_5_a54/}
}
TY  - JOUR
AU  - V. V. Bykova
TI  - Methods for designing FPT-algorithms on graphs of limited treewidth
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2012
SP  - 102
EP  - 104
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/PDMA_2012_5_a54/
LA  - ru
ID  - PDMA_2012_5_a54
ER  - 
%0 Journal Article
%A V. V. Bykova
%T Methods for designing FPT-algorithms on graphs of limited treewidth
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2012
%P 102-104
%N 5
%U http://geodesic.mathdoc.fr/item/PDMA_2012_5_a54/
%G ru
%F PDMA_2012_5_a54
V. V. Bykova. Methods for designing FPT-algorithms on graphs of limited treewidth. Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 102-104. http://geodesic.mathdoc.fr/item/PDMA_2012_5_a54/

[1] Downey R., Fellows M., Parameterized complexity, Springer Verlag, New York, 1999 | MR | Zbl

[2] Bykova V. V., “FPT-algoritmy i ikh klassifikatsiya na osnove elastichnosti”, Prikladnaya diskretnaya matematika, 2011, no. 2(12), 40–48

[3] Bodlaender H. L., “Treewidth: Algorithmic techniques and results”, LNCS, 1295, 1997, 19–36 | MR | Zbl

[4] Niedermeier R., Rossmanith P., “A general method to speed up fixed-parameter-tractable algorithms”, Inform. Proc. Lett., 73 (2000), 125–129 | DOI | MR | Zbl

[5] Bykova V. V., “Vychislitelnye aspekty drevovidnoi shiriny grafa”, Prikladnaya diskretnaya matematika, 2011, no. 3(13), 65–79

[6] Courcelle B., “The monadic second-order logic of graphs. III. Tree decompositions, minors and complexity issues”, RAIRO Inform. Theor. Appl., 26:3 (1992), 257–286 | MR | Zbl

[7] Bykova V. V., “FPT-algoritmy na grafakh ogranichennoi drevovidnoi shiriny”, Prikladnaya diskretnaya matematika, 2012, no. 2(16), 65–78