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

Cеминар лаборатории «Дискретная и вычислительная геометрия им. Б.Н. Делоне» от 21 июня 2013 года.

Докладчик: к.ф.-м.н. Малышев Дмитрий Сергеевич (Нижегородский государственный университет им. Н.И. Лобачевского)

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

Видео (скачать).