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