Перевод названия: 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
Место издания: Томск
Издатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Национальный исследовательский Томский государственный университет
Персоны
- Быкова Валентина Владимировна (Сибирский федеральный университет)
Вхождение в базы данных
- Ядро РИНЦ (eLIBRARY.RU)
- Список ВАК
Информация о публикациях загружается с сайта службы поддержки публикационной активности СФУ. Сообщите, если заметили неточности.