|
Mathematical Foundations of Informatics and Programming
FPT-algorithms and their classification on the base of elasticity
V. V. Bykova Institute of Mathematics, Siberian Federal University, Krasnoyarsk
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.
Full text:
PDF file (482 kB)
References:
PDF file
HTML file
UDC:
510.52+004.051
Citation:
V. V. Bykova, “FPT-algorithms and their classification on the base of elasticity”, Prikl. Diskr. Mat., 2011, supplement № 4, 58–60
Citation in format AMSBIB
\Bibitem{Byk11}
\by V.~V.~Bykova
\paper FPT-algorithms and their classification on the base of elasticity
\jour Prikl. Diskr. Mat.
\yr 2011
\pages 58--60
\issueinfo supplement № 4
\mathnet{http://mi.mathnet.ru/pdm286}
Linking options:
http://mi.mathnet.ru/eng/pdm286 http://mi.mathnet.ru/eng/pdm/y2011/i13/p58
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
|
Number of views: |
This page: | 174 | Full text: | 72 | References: | 42 |
|