FPT-algorithms and their classification on the basis of elasticity

V. V. Bykova

Prikladnaâ diskretnaâ matematika, no. 2 (2011), pp. 40-48.

Résumé

We give a brief overview of the results and problems of parameterized algorithmics as the new direction of computational complexity theory. For a parameterized algorithm, we offer a new indicator of computational complexity which can be used to measure the growth rate of its complexity function depending on many variables. This indicator is a partial elasticity of the complexity function. We offer a two-dimensional classification of parameterized algorithms with the complexity function having a multiplicative form of presentation.

Détail

Keywords: computation complexity, parameterized algorithms, elasticity of algorithms.

Bibliographie

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[2] Ausiello G., Crescenzi P., Gambosi G., et al., Complexity and approximation, combinatorial optimization problems and their approximability properties, Springer Verlag, New York, 1999 | MR | Zbl

[3] Flum J., Grohe M., Parameterized complexity theory, Springer Verlag, Berlin–Heidelberg, 2006 | MR

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

[5] Fellows M., Koblitz N., Fixed-parameter complexity and cryptography, Technical Report DCS-207-IR, Department of Comput. Science, University of Victoria, 1992 | MR

[6] Gottlob G., Scarcello F., Sideri M., “Fixed-parameter complexity in AI and Nonmonotonic reasoning”, Artific. Intellig., 138 (2002), 55–86 | DOI | MR | Zbl

[7] Bodlaender H., Downey R., Fellows M., et al., “Parameterized complexity analysis in computational biology”, Comput. Appl. Bioscien., 11 (1995), 49–57

[8] Papadimitriou C., Yannakakis M., “On the complexity of database queries”, J. Comput. System Scien., 58 (1999), 407–427 | DOI | MR | Zbl

[9] Niedermeier R., Invitation to fixed-parameter algorithms, Oxford Lecture series in mathematics and its applications, University Press, Oxford, 2006 | MR | Zbl

[10] Cesati M., Compendium of parameterized problems, , 2006 http://bravo.ce.uniroma2.it/home/cesati/research/compendium

[11] Gottlob G., Pichler R., Wei F., “Abduction with bounded treewidth: From theoretical tractability to practically efficient computation”, Proc. of the Twenty-Third AAAI Conf. on Artificial Intelligence, AAAI Press, Menlo Park, 2008, 1541–1546

[12] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, MTsNMO, M., 1999

[13] Grin D., Knut D., Matematicheskie metody analiza algoritmov, Mir, M., 1987 | MR

[14] Bykova V. V., “Matematicheskie metody analiza rekursivnykh algoritmov”, Zhurn. SFU. Matematika i fizika, 1:3 (2008), 236–246

[15] Bykova V. V., “Metod raspoznavaniya klassov algoritmov na osnove asimptotiki elastichnosti funktsii slozhnosti”, Zhurn. SFU. Matematika i fizika, 2:1 (2009), 48–62

[16] Bykova V. V., “Elastichnost algoritmov”, Prikladnaya diskretnaya matematika, 2010, no. 2(8), 87–95

[17] Bykova V. V., “Complexity and elasticity of the computation”, Proc. of the 3-rd IASTED International Multi-Conference on Automation, Control, and Information Technology (ACIT-CDA 2010), ACTA Press, Anaheim–Calgary–Zurich, 2010, 334–340

[18] Grekhem R., Knut D., Potashnik O., Konkretnaya matematika, Mir, Binom. Laboratoriya znanii, M., 2006