ГлавнаяАрхивFPT-алгоритмы и их классификация на основе эластичности

FPT-алгоритмы и их классификация на основе эластичности | Прикладная дискретная математика. 2011. № 2(12).

Приведены основные положения и проблемы параметризированной алгоритмики - нового направления теории сложности вычислений. Предложен новый показатель вычислительной сложности параметризированного алгоритма, с помощью которого можно измерять темп роста функции сложности многих переменных. Этим показателем является частная эластичность функции сложности. Предложена двумерная классификация параметризированных алгоритмов для мультипликативной формы представления функций сложности.
  • Title FPT-алгоритмы и их классификация на основе эластичности
  • Headline FPT-алгоритмы и их классификация на основе эластичности
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(12)
  • Date:
  • DOI
Ключевые слова
elasticity of algorithms, computation complexity, parameterized algorithms, эластичность алгоритмов, анализ алгоритмов, параметризированные алгоритмы, сложность вычислений
Авторы
Ссылки
Грэхем Р., Кнут Д., Поташник О. Конкретная математика. М.: Мир; Бином. Лаборатория знаний, 2006.
Bykova V. V. Complexity and elasticity of the computation // Proc. of the 3-rd IASTED International Multi-Conference on Automation, Control, and Information Technology (ACITCDA 2010). Anaheim-Calgary-Zurich: ACTA Press, 2010. P. 334-340.
Быкова В. В. Эластичность алгоритмов // Прикладная дискретная математика. 2010. №2(8). С. 87-95.
Быкова В. В. Метод распознавания классов алгоритмов на основе асимптотики эластич- ности функций сложности // Журн. СФУ. Математика и физика. 2009. №2(1). С. 46-61.
Грин Д., Кнут Д. Математические методы анализа алгоритмов. М.: Мир, 1987.
Быкова В. В. Математические методы анализа рекурсивных алгоритмов // Журн. СФУ. Математика и физика. 2008. №1(3). С. 236-246.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.
CesatiM. Compendium of parameterized problems. http://bravo.ce.uniroma2.it/home/ cesati/research/compendium - 2006.
Gottlob G., PichlerR., and Wei F. Abduction with bounded treewidth: From theoretical tractability to practically efficient computation // Proc. of the Twenty-Third AAAI Conf. on Artificial Intelligence. Menlo Park: AAAI Press, 2008. P. 1541-1546.
Niedermeier R. Invitation to fixed-parameter algorithms: Oxford Lecture series in mathematics and its applications. Oxford: University Press, 2006.
Bodlaender H., Downey R., Fellows M., et al. Parameterized complexity analysis in computational biology // Comput. Appl. Bioscien. 1995. V. 11. P. 49-57.
Papadimitriou C. and Yannakakis M. On the complexity of database queries / / J . Comput. System Scien. 1999. V. 58. P. 407-427.
Fellows M. and Koblitz N. Fixed-parameter complexity and cryptography // Technical Report DCS-207-IR, Department of Comput. Science, University of Victoria, 1992.
Gottlob G., Scarcello F., and Sideri M. Fixed-parameter complexity in AI and Nonmonotonic reasoning // Artific. Intellig. 2002. V. 138. P. 55-86.
Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
Ausiello G., Crescenzi P., Gambosi G., et al. Complexity and approximation, combinatorial optimization problems and their approximability properties. New York: Springer Verlag, 1999.
Flum J. and Grohe M. Parameterized complexity theory. Berlin; Heidelberg: Springer Verlag, 2006.
Downey R. and Fellows M. Parameterized complexity. New York: Springer Verlag, 1999.
FPT-алгоритмы и их классификация на основе эластичности | Прикладная дискретная математика. 2011. № 2(12).
FPT-алгоритмы и их классификация на основе эластичности | Прикладная дискретная математика. 2011. № 2(12).
Полнотекстовая версия