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

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




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


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

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

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

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

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