|
|
Межкафедральный семинар МФТИ по дискретной математике
26 ноября 2014 г. 18:35, г. Долгопрудный, МФТИ, Корпус Прикладной Математики, 115
|
|
|
|
|
|
Древесная ширина (treewidth)
Тихомиров Михаил Игоревич Московский физико-технический институт (государственный университет), г. Долгопрудный Московской обл.
|
Количество просмотров: |
Эта страница: | 276 |
|
Аннотация:
Формально говоря, древесная ширина — это минимальный размер древесной декомпозиции графа (специальной системы подмножеств вершин с древесной структурой на ней). Для графов с маленькой древесной шириной существуют общие подходы, позволяющие строить быстрые алгоритмы для таких сложных в общем случае задач, как раскрашивание графа, нахождение числа независимости или проверка изоморфизма; это тем более интересно, что для некоторых классов графов можно построить небольшую древесную композицию и получить вполне практическое решение задачи. Помимо этого, мы сформулируем некоторые теоретические результаты, устанавливающие связь между древесной шириной графа и его локальной структурой.
|
|