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

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





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








Межкафедральный семинар МФТИ по дискретной математике
26 ноября 2014 г. 18:35, г. Долгопрудный, МФТИ, Корпус Прикладной Математики, 115
 


Древесная ширина (treewidth)

Тихомиров Михаил Игоревич

Московский физико-технический институт (государственный университет), г. Долгопрудный Московской обл.

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

Аннотация: Формально говоря, древесная ширина — это минимальный размер древесной декомпозиции графа (специальной системы подмножеств вершин с древесной структурой на ней). Для графов с маленькой древесной шириной существуют общие подходы, позволяющие строить быстрые алгоритмы для таких сложных в общем случае задач, как раскрашивание графа, нахождение числа независимости или проверка изоморфизма; это тем более интересно, что для некоторых классов графов можно построить небольшую древесную композицию и получить вполне практическое решение задачи. Помимо этого, мы сформулируем некоторые теоретические результаты, устанавливающие связь между древесной шириной графа и его локальной структурой.

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