RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2011 Number 2(12), Pages 40–48 (Mi pdm274)

This article is cited in 5 papers

Mathematical Foundations of Informatics and Programming

FPT-algorithms and their classification on the basis of elasticity

V. V. Bykova

Institute of Mathematics, Siberian Federal University, Krasnoyarsk, Russia

Abstract: 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.

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

UDC: 510.52+004.051



© Steklov Math. Inst. of RAS, 2024