RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Межкафедральный семинар МФТИ по дискретной математике
25 сентября 2013 г. 18:30–20:00, г. Долгопрудный, МФТИ, Корпус Прикладной Математики, 115
 


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

Д. С. Малышев

Количество просмотров:
Эта страница:90

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

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020