Перевод названия: FPT-algorithms and their classification on the basis of elasticity
Тип публикации: статья из журнала
Год издания: 2011
Ключевые слова: эластичность алгоритмов, Computation complexity, Parameterized algorithms, elasticity of algorithms, сложность вычислений, параметризированные алгоритмы, анализ алгоритмов
Аннотация: Приведены основные положения и проблемы параметризированной алгоритмики - нового направления теории сложности вычислений. Предложен новый показатель вычислительной сложности параметризированного алгоритма, с помощью которого можно измерять темп роста функции сложности многих переменных. Этим показателем является частная эластичностПоказать полностьюь функции сложности. Предложена двумерная классификация параметризированных алгоритмов для мультипликативной формы представления функций сложности. 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 twodimensional classification of parameterized algorithms with the complexity function having a multiplicative form of presentation.
Журнал: Прикладная дискретная математика
Выпуск журнала: № 2
Номера страниц: 40-48
ISSN журнала: 20710410
Место издания: Томск
Издатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Национальный исследовательский Томский государственный университет