Нежное введение в алгоритмические аспекты глубины дерева

13

Treewidth и pathwidth являются популярными параметрами, измеряющими близость графа к дереву или пути, соответственно. В самом деле, кажется, что древовидная ширина настолько популярна, что во многих статьях, книгах и конспектах лекций, которые (даже очень осторожно) знакомят с алгоритмическими аспектами древовидной структуры (см., Например, книгу Дауни и сотрудников). Как правило, эти ресурсы объясняют, как некоторая NP-сложная задача (например, независимое множество) решается за полиномиальное время посредством динамического программирования разложения дерева.

Тем не менее, иногда возникает проблема, когда граф остается NP-полным для графов с ограниченной шириной и шириной пути. Но такие результаты твердости не подразумевают твердость для ограниченной глубины дерева , которая неофициально измеряет близость к звезде.

Кажется справедливым сказать, что глубина дерева не так широко известна, как ширина дерева. Для кого-то, кто хочет узнать больше об алгоритмах, параметризованных по глубине дерева, есть ли (аналогично treewidth) какие-нибудь приятные ресурсы, доступные для изучения того, как такие алгоритмы обычно работают?

Юхо
источник

Ответы:

10

Мой любимый ресурс для этой темы является книгой разреженности по Ярославу Несетрил и Патрис Ossona де Мендес. В нем довольно много материала конкретно о глубине дерева, включая алгоритмические аспекты. И для более краткого и быстрого введения, всегда есть статья в Википедии .

Дэвид Эппштейн
источник
@Juho Кроме того, глава 6 книги « Раскраски графа» посвящена ранжированию вершин (также называемой упорядоченной раскраской). Глубина дерева такая же, как хроматическое число этого варианта окраски. В главе книги описаны простые алгоритмы (например, на деревьях).
Кириак Антоний