26 сентября 2013 г.

  Д.С. Малышев (НИУ ВШЭ-НН и ННГУ)

"Исследование "критических" наследственных классов в анализе вычислительной сложности задач на графах"

Развитие теории сложности вычислений способствовало укоренению пессимистического взгляда на возможность существования эффективных (полиномиальных) алгоритмов для многих задач на графах, представляющих практический и/или теоретический интерес. Одним из способов преодоления алгоритмической сложности таких задач является сужение, т.е. наложение дополнительных ограничений на класс рассматриваемых графов. Иногда учет этих ограничений приводит к созданию полиномиального алгоритма для решения задачи. В других случаях удается доказать, что задача для графов из того или иного класса остается NP-полной. К настоящему времени накоплено огромное количество фактов того и иного рода. Придать этому процессу целенаправленность и систематичность можно переходя от рассмотрения отдельных классов к рассмотрению представительных семейств классов. В докладе будут изложены результаты докторской диссертации автора по поиску «линии водораздела» между «простыми» и «сложными» элементами семейства наследственных классов графов.

Наверх