Ширина дерева

В теории графов древовидная ширина неориентированного графа — это целое число, которое неформально указывает, насколько граф далек от того, чтобы быть деревом . Наименьшая древовидная ширина равна 1; графы с древовидной шириной 1 — это в точности деревья и леса . Графы с древовидной шириной не более 2 — это последовательно-параллельные графы . Максимальные графы с древовидной шириной точно $k$ называются $k$ -деревьями , а графы с древовидной шириной не более $k$ называются частичными $k$ -деревьями . ^[1] Многие другие хорошо изученные семейства графов также имеют ограниченную древовидную ширину.

Ширина дерева может быть формально определена несколькими эквивалентными способами: в терминах размера наибольшего множества вершин в древовидной декомпозиции графа, в терминах размера наибольшей клики в хордовом завершении графа, в терминах максимального порядка убежища , описывающего стратегию для игры преследования-уклонения на графе, или в терминах максимального порядка ежевики , набора связанных подграфов, которые все касаются друг друга.

Ширина дерева обычно используется как параметр в параметризованном анализе сложности графовых алгоритмов . Многие алгоритмы, которые являются NP-трудными для общих графов, становятся проще, когда ширина дерева ограничена константой.

Концепция ширины дерева была первоначально введена Умберто Бертеле и Франческо Бриоски (1972) под названием размерность . Позднее она была переоткрыта Рудольфом Халином (1976) на основе свойств, которые она разделяет с другим параметром графа, числом Хадвигера . Позже она была снова переоткрыта Нилом Робертсоном и Полом Сеймуром (1984) и с тех пор изучалась многими другими авторами. ^[2]

Определение

Древовидная декомпозиция графа $G = (V, E)$ — это дерево $T$ с узлами $X 1, \dots, X n$ , где каждый $X i$ является подмножеством $V$ , удовлетворяющим следующим свойствам ^[3] (термин узел используется для обозначения вершины $T ,$ чтобы избежать путаницы с вершинами $G$ ):

Объединение всех множеств $X i$ равно $V.$ То есть каждая вершина графа содержится по крайней мере в одном узле дерева.
Если $X i$ и $X j$ оба содержат вершину $v$ , то все узлы $X k$ из $T$ в (уникальном) пути между $X i$ и $X j$ также содержат $v . Эквивалентно, узлы дерева, содержащие вершину$ $v,$ образуют связное поддерево $T$ .
Для каждого ребра $(v, w)$ в графе существует подмножество $X i$ , содержащее как $v,$ так и $w$ . То есть вершины являются смежными в графе только тогда, когда соответствующие поддеревья имеют общий узел.

Ширина древовидной декомпозиции — это размер ее наибольшего множества $X$ $i$ минус один. Древовидная ширина $tw($ $G$ $)$ графа $G$ — это минимальная ширина среди всех возможных древовидных декомпозиций $G$ . В этом определении размер наибольшего множества уменьшается на единицу, чтобы сделать древовидную ширину дерева равной единице.

Эквивалентно, ширина дерева $G$ на единицу меньше размера наибольшей клики в хордальном графе, содержащем $G$ с наименьшим номером клики . Хордальный граф с таким размером клики может быть получен путем добавления к $G$ ребра между каждыми двумя вершинами, которые обе принадлежат хотя бы одному из множеств $X i$ .

Древовидную ширину также можно охарактеризовать в терминах убежищ , функций, описывающих стратегию уклонения для определенной игры преследования-уклонения, определенной на графе. Граф $G$ имеет древовидную ширину $k$ тогда и только тогда, когда у него есть убежище порядка $k + 1$ , но не более высокого порядка, где убежище порядка $k + 1$ — это функция $β$ , которая отображает каждое множество $X$ из не более чем $k$ вершин в $G$ в одну из связных компонент $G \ X$ и которая подчиняется свойству монотонности , что $β (Y) \subseteq β (X)$ всякий раз, когда $X \subseteq Y$ .

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

Примеры

Каждый полный граф $K n$ имеет древесную ширину $n$ $- 1.$ Это легче всего увидеть, используя определение древесной ширины в терминах хордовых графов: полный граф уже является хордовым, и добавление большего количества ребер не может уменьшить размер его наибольшей клики.

Связный граф с по крайней мере двумя вершинами имеет древесную ширину 1 тогда и только тогда, когда он является деревом. Дерево имеет древесную ширину один по тем же соображениям, что и для полных графов (а именно, оно хордальное и имеет максимальный размер клики два). Обратно, если граф имеет цикл, то каждое хордовое завершение графа включает по крайней мере один треугольник, состоящий из трех последовательных вершин цикла, из чего следует, что его древесная ширина равна по крайней мере двум.

Ограниченная ширина дерева

Семейства графов с ограниченной шириной дерева

Для любой фиксированной константы $k$ графы с древовидной шириной не более $k$ называются частичными $k$ -деревьями . Другие семейства графов с ограниченной древовидной шириной включают кактусовые графы , псевдолеса , последовательно-параллельные графы , внешнепланарные графы , графы Халина и сети Аполлона . ^[5] Графы потока управления, возникающие при компиляции структурированных программ , также имеют ограниченную древовидную ширину, что позволяет эффективно выполнять на них определенные задачи, такие как распределение регистров . ^[6]

Планарные графы не имеют ограниченной древесной ширины, поскольку граф сетки $n \times n$ является планарным графом с древесной шириной ровно $n$ . Следовательно, если $F$ является замкнутым по минорам семейством графов с ограниченной древесной шириной, оно не может включать все планарные графы. И наоборот, если некоторый планарный граф не может встречаться как минор для графов в семействе $F$ , то существует константа $k$ такая, что все графы в $F$ имеют древесную ширину не более $k$ . То есть, следующие три условия эквивалентны друг другу: ^[7]

$F$ — это замкнутое по минору семейство графов ограниченной древовидной ширины;
Один из конечного числа запрещенных миноров, характеризующих $F$ , является планарным;
$F$ — семейство минорно-замкнутых графов, которое не включает в себя все планарные графы.

Запрещенные несовершеннолетние

Для каждого конечного значения $k$ графы древесной ширины не более $k$ могут быть охарактеризованы конечным набором запрещённых миноров . (То есть любой граф древесной ширины $> k$ включает в себя один из графов в наборе в качестве минора.) Каждый из этих наборов запрещённых миноров включает в себя по крайней мере один планарный граф.

При $k = 1$ единственный запрещенный минор представляет собой граф-цикл с 3 вершинами . ^[5]
При $k = 2$ единственным запрещенным минором является полный граф $K 4$ с 4 вершинами . ^[5]
Для $k = 3$ существует четыре запрещенных минора: $K 5$ , граф октаэдра , граф пентагональной призмы и граф Вагнера . Из них два многогранных графа являются планарными. ^[8]

Для больших значений $k$ число запрещенных миноров растет по крайней мере так же быстро, как экспонента квадратного корня из $k$ . ^[9] Однако известные верхние границы размера и числа запрещенных миноров намного выше этой нижней границы. ^[10]

Алгоритмы

Вычисление ширины дерева

Это NP-полная задача, чтобы определить, имеет ли заданный граф $G$ древовидную ширину не более заданной переменной $k$ . ^[11] Однако, когда $k$ является любой фиксированной константой, графы с древовидной шириной $k$ могут быть распознаны, и для них может быть построена древовидная декомпозиция ширины $k$ за линейное время. ^[12] Зависимость этого алгоритма от времени $k$ является экспоненциальной.

Из-за ролей, которые древовидная ширина играет в огромном количестве областей, были разработаны различные практические и теоретические алгоритмы вычисления древовидной ширины графа. В зависимости от приложения можно предпочесть лучшее отношение аппроксимации или лучшую зависимость времени выполнения от размера входных данных или древовидной ширины. В таблице ниже представлен обзор некоторых алгоритмов древовидной ширины. Здесь $k$ — древовидная ширина, а $n$ — количество вершин входного графа $G.$ Каждый из алгоритмов выводит за время $f (k) \cdot g (n)$ разложение ширины, указанное в столбце «Аппроксимация». Например, алгоритм Бодлендера (1996) за время $2 O (k 3) \cdot n$ либо строит древовидную разложение входного графа $G$ шириной не более $k ,$ либо сообщает, что древовидная ширина $G$ больше $k$ . Аналогично, алгоритм Бодлендера и др. (2016) за время $2 O (k) \cdot n$ либо строит древовидную декомпозицию входного графа $G$ шириной не более $5 k + 4$ , либо сообщает, что древовидная ширина $G$ больше $k$ . Корхонен (2021) улучшил это до $2 k + 1$ за то же время выполнения.

Нерешенная задача по математике :

Можно ли вычислить ширину дерева планарных графов за полиномиальное время?

(еще нерешенные проблемы по математике)

Неизвестно, является ли определение ширины дерева планарных графов NP-полной задачей или их ширина дерева может быть вычислена за полиномиальное время. ^[13]

На практике алгоритм Шойхета и Гейгера (1997) позволяет определить ширину дерева графов с числом вершин до 100 и шириной дерева до 11, находя хордовое завершение этих графов с оптимальной шириной дерева.

Для более крупных графов можно использовать методы поиска, такие как поиск ветвей и границ (BnB) и поиск по лучшему первому, чтобы вычислить ширину дерева. Эти алгоритмы всегда в том, что при ранней остановке они выведут верхнюю границу ширины дерева.

Первый алгоритм BnB для вычисления древовидной ширины, называемый алгоритмом QuickBB ^[14], был предложен Гогатом и Дехтером. ^[15] Поскольку качество любого алгоритма BnB сильно зависит от качества используемой нижней границы, Гогат и Дехтер ^[15] также предложили новый алгоритм для вычисления нижней границы древовидной ширины, называемый minor-min-width. ^[15] На высоком уровне алгоритм minor-min-width объединяет факты о том, что древовидная ширина графа никогда не превышает его минимальной степени или его минора , чтобы получить нижнюю границу древовидной ширины. Алгоритм minor-min-width многократно строит минор графа , стягивая ребро между вершиной минимальной степени и одним из ее соседей, пока не останется только одна вершина. Максимум минимальной степени по этим построенным минорам гарантированно будет нижней границей древовидной ширины графа.

Доу и Корф ^[16] улучшили алгоритм QuickBB, используя поиск по лучшему первому совпадению . На некоторых графах этот алгоритм поиска по лучшему первому совпадению на порядок быстрее, чем QuickBB.

Решение других задач на графах малой древовидной ширины

В начале 1970-х годов было замечено, что большой класс задач комбинаторной оптимизации, определенных на графах, может быть эффективно решен с помощью не последовательного динамического программирования , пока граф имеет ограниченную размерность ^[17] , параметр, который, как показал Бодлендер (1998), эквивалентен древовидной ширине. Позднее, в конце 1980-х годов ^[18], несколько авторов независимо друг от друга заметили , что многие алгоритмические задачи, которые являются NP-полными для произвольных графов, могут быть эффективно решены с помощью динамического программирования для графов с ограниченной древовидной шириной, используя древовидные разложения этих графов.

Например, задача раскраски графа древовидной ширины $k$ может быть решена с помощью алгоритма динамического программирования на древовидной декомпозиции графа. Для каждого множества $X i$ древовидной декомпозиции и каждого разбиения вершин $X i$ на цветовые классы алгоритм определяет, является ли эта раскраска допустимой и может ли она быть распространена на все дочерние узлы в древовидной декомпозиции, путем объединения информации аналогичного типа, вычисленной и сохраненной в этих узлах. Полученный алгоритм находит оптимальную раскраску $n-$ вершинного графа за время $O (k k + O (1) n)$ , ограничение по времени, которое делает эту задачу разрешимой с фиксированным параметром .

Теорема Курселя

Для большого класса задач существует алгоритм линейного времени для решения задачи из класса, если предоставлена древовидная декомпозиция с постоянной ограниченной древовидной шириной. В частности, теорема Курселя ^[19] утверждает, что если графовая задача может быть выражена в логике графов с использованием монадической логики второго порядка , то она может быть решена за линейное время на графах с ограниченной древовидной шириной. Монадическая логика второго порядка — это язык для описания свойств графов, который использует следующие конструкции:

Логические операции, такие как $\wedge ,\vee ,\neg ,\Rightarrow$
Тесты на принадлежность, такие как $e \in E$ , $v \in V$
Квантификации по вершинам, ребрам, наборам вершин и/или наборам ребер, такие как $\forall v \in V$ , $\exists e \in E$ , $\exists I \subseteq V$ , $\forall F \subseteq E$
Тесты смежности ( $u$ — конечная точка $e$ ) и некоторые расширения, которые позволяют выполнять такие операции, как оптимизация.

Рассмотрим, например, задачу 3-раскраски для графов. Для графа $G = (V, E)$ эта задача спрашивает, возможно ли назначить каждой вершине $v \in V$ один из 3 цветов так, чтобы никаким двум смежным вершинам не был назначен один и тот же цвет. Эту задачу можно выразить в монадической логике второго порядка следующим образом:

\exists W_{1}\subseteq V:\exists W_{2}\subseteq V:\exists W_{3}\subseteq V:\forall v\in V:(v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge

\forall v\in V:\forall w\in V:(v,w)\in E\Rightarrow (\neg (v\in W_{1}\wedge w\in W_{1})\wedge \neg (v\in W_{2}\wedge w\in W_{2})\wedge \neg (v\in W_{3}\wedge w\in W_{3}))

где $W 1$ , $W 2$ , $W 3$ представляют подмножества вершин, имеющих каждый из 3 цветов. Следовательно, согласно результатам Курселя, задача 3-раскраски может быть решена за линейное время для графа, заданного древовидной декомпозицией ограниченной постоянной древовидной ширины.

Связанные параметры

Ширина пути

Ширина пути графа имеет очень похожее определение с древовидной шириной через древовидные декомпозиции, но ограничена древовидными декомпозициями, в которых базовое дерево декомпозиции является путевым графом . В качестве альтернативы, ширина пути может быть определена из интервальных графов аналогично определению древовидной ширины из хордовых графов. Как следствие, ширина пути графа всегда по крайней мере такая же большая, как его древовидная ширина, но она может быть больше только на логарифмический множитель. ^[5] Другой параметр, ширина полосы графа , имеет аналогичное определение из правильных интервальных графов и по крайней мере такая же большая, как путевая ширина. Другие связанные параметры включают глубину дерева , число, которое ограничено для семейства графов с минорной замкнутостью тогда и только тогда, когда семейство исключает путь, и вырожденность , меру разреженности графа, которая не больше его древовидной ширины.

Размер ячейки сетки

Поскольку ширина дерева графа сетки $n \times n$ равна $n$ , ширина дерева графа $G$ всегда больше или равна размеру наибольшего квадратного минора сетки $G$ . С другой стороны, теорема Робертсона и Сеймура о миноре сетки показывает, что существует неограниченная функция $f$ такая, что наибольший квадратный минор сетки имеет размер не менее $f$ $($ $r$ $)$ , где $r$ — ширина дерева. ^[20] Наилучшие известные границы для f $заключаются$ в том, что $f$ должна быть не менее $Ω($ $r$ $d$ $)$ для некоторой фиксированной константы $d$ $> 0$ и не более ^[21]

O\left({\sqrt {r/\log r}}\right).

Для обозначения $Ω$ в нижней границе см . обозначение big O. Более строгие границы известны для ограниченных семейств графов, что приводит к эффективным алгоритмам для многих задач оптимизации графов на этих семействах с помощью теории двумерности . ^[22]Теорема Халина о сетке дает аналог соотношения между шириной дерева и малым размером сетки для бесконечных графов. ^[23]

Диаметр и локальная ширина дерева

Говорят, что семейство графов $F , замкнутое относительно взятия подграфов, имеет$ ограниченную локальную древесную ширину или свойство диаметр-древесная ширина , если древесная ширина графов в семействе ограничена сверху функцией их диаметра . Если класс также предполагается замкнутым относительно взятия миноров , то $F$ имеет ограниченную локальную древесную ширину тогда и только тогда, когда один из запрещенных миноров для $F$ является графом вершины . ^[24] Первоначальные доказательства этого результата показали, что древесная ширина в семействе графов, свободных от миноров вершины, растет не более чем дважды экспоненциально как функция диаметра; ^[25] позже это было сведено к одинарной экспоненциальной ^[22] и, наконец, к линейной границе. ^[26] Ограниченная локальная ширина дерева тесно связана с алгоритмической теорией двумерности , ^[27] и каждое свойство графа, определяемое в логике первого порядка, может быть определено для семейства графов без вершин и миноров за время, которое лишь немного сверхлинейно. ^[28]

Также возможно, что класс графов, не замкнутый относительно миноров, имеет ограниченную локальную древовидную ширину. В частности, это тривиально верно для класса графов ограниченной степени, поскольку подграфы ограниченного диаметра имеют ограниченный размер. Другой пример дают 1-планарные графы , графы, которые можно нарисовать на плоскости с одним пересечением на ребро, и, в более общем смысле, графы, которые можно нарисовать на поверхности ограниченного рода с ограниченным числом пересечений на ребро. Как и в случае с семействами графов, замкнутых относительно миноров, с ограниченной локальной древовидной шириной, это свойство указало путь к эффективным алгоритмам аппроксимации для этих графов. ^[29]

Число Хадвигера иС-функции

Халин (1976) определяет класс параметров графа, которые он называет $S$ -функциями, которые включают ширину дерева. Эти функции из графов в целые числа должны быть равны нулю на графах без ребер , быть минорно-монотонными (функция $f$ называется «минорно-монотонной», если всякий раз, когда $H$ является минором $G$ , выполняется $f (H ) \leq f (G)$ ), увеличиваться на единицу при добавлении новой вершины, смежной со всеми предыдущими вершинами , и принимать большее значение из двух подграфов по обе стороны от разделителя клик . Набор всех таких функций образует полную решетку при операциях поэлементной минимизации и максимизации. Верхний элемент в этой решетке — ширина дерева, а нижний элемент — число Хадвигера , размер наибольшего полного минора в данном графе.

Примечания

^ Бодлендер (1988).
^ Дистель (2005) стр.354–355
^ Дистель (2005) раздел 12.3
^ Сеймур и Томас (1993).
^ abcd Бодлендер (1998).
^ Торуп (1998).
^ Робертсон и Сеймур (1986).
^ Арнборг, Проскуровски и Корнейл (1990); Сатьянараяна и Тунг (1990).
^ Рамачандрамурти (1997).
^ Лагергрен (1993).
^ Арнборг, Корнейл и Проскуровски (1987).
^ Бодлендер (1996).
^ Као (2008).
^ "Вибхав Гогате". Personal.utdallas.edu . Проверено 27 ноября 2022 г.
^ abc Gogate, Vibhav; Dechter, Rina (2012-07-11). "Полный алгоритм для ширины дерева в любое время". arXiv : 1207.4109 [cs.DS].
^ "Best-First Search for Treewidth". www.aaai.org . Получено 2022-11-27 .
^ Бертеле и Бриоски (1972).
^ Арнборг и Проскуровски (1989); Берн, Лоулер и Вонг (1987); Бодлендер (1988).
^ Курсель (1990); Курсель (1992)
^ Робертсон, Сеймур. Миноры графа. V. Исключение планарного графа . [1]
^ Чекури и Чужой (2016)
^ аб Демейн и Хаджиагайи (2008).
^ Дистель (2004).
^ Эппштейн (2000).
^ Эппштейн (2000); Демейн и Хаджиагайи (2004a).
^ Демейн и Хаджиагайи (2004b).
^ Демейн и др. (2004); Демейн и Хаджиагайи (2008).
^ Фрик и Гроэ (2001).
^ Григорьев и Бодлендер (2007).

Ссылки

Амир, Эяль (2010), «Алгоритмы аппроксимации для ширины дерева», Algorithmica , 56 (4): 448–479, doi :10.1007/s00453-008-9180-4, MR 2581059, S2CID 5874913.
Арнборг, С.; Корнейл, Д .; Проскуровски, А. (1987), «Сложность поиска вложений в -дерево » , SIAM Journal on Matrix Analysis and Applications , 8 (2): 277–284, doi :10.1137/0608024 $k$ .
Арнборг, Стефан; Проскуровски, Анджей; Корнейл, Дерек Г. (1990), «Характеристика частичных 3-деревьев с помощью запрещенных миноров», Дискретная математика , 80 (1): 1–19, doi : 10.1016/0012-365X(90)90292-P , MR 1045920.
Арнборг, С.; Проскуровски, А. (1989), "Линейные алгоритмы для NP-трудных задач, ограниченных частичными -деревьями ", Дискретная прикладная математика , 23 (1): 11–24, doi : 10.1016/0166-218X(89)90031-0 $k$ .
Belbasi, Mahdi; Fürer, Martin (2021a), «Улучшение аппроксимации ширины дерева Рида», в Uehara, Ryuhei; Hong, Seok-Hee ; Nandy, Subhas C. (ред.), WALCOM: алгоритмы и вычисления – 15-я международная конференция и семинары, WALCOM 2021, Янгон, Мьянма, 28 февраля - 2 марта 2021 г., Труды , Lecture Notes in Computer Science, т. 12635, Springer, стр. 166–181, arXiv : 2010.03105 , doi : 10.1007/978-3-030-68211-8_14, ISBN 978-3-030-68210-1, MR 4239527, S2CID 222177100.
Belbasi, Mahdi; Fürer, Martin (2021b), «Нахождение всех самых левых разделителей размера », в Du, Ding-Zhu; Du, Donglei; Wu, Chenchen; Xu, Dachuan (ред.), Combinatory Optimization and Applications - 15th International Conference, COCOA 2021, Tianjin, China, December 17-19, 2021, Proceedings , Lecture Notes in Computer Science, vol. 13135, Springer, pp. 273–287, arXiv : 2111.02614 , doi : 10.1007/978-3-030-92681-6_23, ISBN $\leq k$ 978-3-030-92680-9, S2CID 242758210
Берн, М. В.; Лоулер, Э. Л .; Вонг, А. Л. (1987), «Вычисление оптимальных подграфов разложимых графов за линейное время», Журнал алгоритмов , 8 (2): 216–235, doi :10.1016/0196-6774(87)90039-3.
Бертеле, Умберто; Бриоски, Франческо (1972), Непоследовательное динамическое программирование, Academic Press, стр. 37–38, ISBN 978-0-12-093450-8.
Bodlaender, Hans L. (1988), "Динамическое программирование на графах с ограниченной древовидной шириной", Proc. 15th International Colloquium on Automata, Languages and Programming , Lecture Notes in Computer Science, т. 317, Springer-Verlag, стр. 105–118, CiteSeerX 10.1.1.18.8503 , doi :10.1007/3-540-19488-6_110, ISBN 978-3-540-19488-0.
Бодлендер, Ханс Л. (1996), «Линейный алгоритм времени для поиска древовидных декомпозиций малой древовидной ширины», SIAM Journal on Computing , 25 (6): 1305–1317, CiteSeerX 10.1.1.19.7484 , doi :10.1137/S0097539793251219.
Бодлендер, Ханс Л. (1998), «Частичный k -дендрарий графов с ограниченной древовидной шириной», Теоретическая информатика , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228-4.
Bodlaender, Hans L.; Drange, Pal G.; Dregi, Markus S.; Fomin, Fedor V.; Lokshtanov, Daniel; Pilipczuk, Michal (2016), " 5-аппроксимационный алгоритм для ширины дерева", SIAM Journal on Computing , 45 (2): 317–378, arXiv : 1304.6321 , doi : 10.1137/130947374 $c^{k}n$ .
Чекури, Чандра; Чужой, Юлия (2016), «Полиномиальные оценки для теоремы о миноре сетки», Журнал ACM , 63 (5): A40:1–65, arXiv : 1305.6577 , doi : 10.1145/2820609, MR 3593966, S2CID 209860422.
Курсель, Б. (1990), «Монадическая логика второго порядка графов I: Распознаваемые множества конечных графов», Информация и вычисления , 85 : 12–75, CiteSeerX 10.1.1.158.5595 , doi :10.1016/0890-5401(90)90043-h.
Курсель, Б. (1992), «Монадическая логика второго порядка графов III: ширина дерева, запрещенные миноры и проблемы сложности», Informatique Théorique (26): 257–286.
Demaine, Erik D .; Fomin, Fedor V.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2004), «Двумерные параметры и локальная ширина дерева», SIAM Journal on Discrete Mathematics , 18 (3): 501–511, CiteSeerX 10.1.1.107.6195 , doi :10.1137/S0895480103433410, MR 2134412, S2CID 7803025.
Демейн, Эрик Д.; Хаджиагайи, МохаммадТаги (2004a), «Диаметр и ширина дерева в семействах минорно-замкнутых графов, пересмотр», Algorithmica , 40 (3): 211–215, doi :10.1007/s00453-004-1106-1, MR 2080518, S2CID 390856.
Демейн, Эрик Д.; Хаджиагайи, МохаммадТаги (2004b), «Эквивалентность локальной древовидной ширины и линейной локальной древовидной ширины и ее алгоритмические приложения», Труды пятнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Нью-Йорк: ACM, стр. 840–849, MR 2290974.
Демейн, Эрик Д.; Хаджиагайи, МохаммадТаги (2008), «Линейность миноров сетки в древовидной ширине с приложениями через двумерность» (PDF) , Combinatorica , 28 (1): 19–36, doi :10.1007/s00493-008-2140-4, S2CID 16520181.
Дистель, Рейнхард (2004), «Краткое доказательство теоремы Халина о сетке», Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 74 : 237–242, doi : 10.1007/BF02941538, MR 2112834, S2CID 124603912.
Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 978-3-540-26182-7.
Эппштейн, Д. (2000), «Диаметр и ширина дерева в семействах минорно-замкнутых графов», Algorithmica , 27 (3–4): 275–291, arXiv : math/9907126 , doi : 10.1007/s004530010020, MR 1759751, S2CID 3172160.
Файге, Уриэль; Хаджиагайи, МохаммадТаги; Ли, Джеймс Р. (2008), «Улучшенные алгоритмы аппроксимации для разделителей вершин с минимальным весом», SIAM Journal on Computing , 38 (2): 629–657, CiteSeerX 10.1.1.597.5634 , doi :10.1137/05064299X.
Фомин, Федор В .; Тодинка, Иоан; Вилланджер, Ингве (2015), «Большие индуцированные подграфы с помощью триангуляции и CMSO», SIAM Journal on Computing , 44 (1): 54–87, arXiv : 1309.1559 , doi : 10.1137/140964801, S2CID 15880453.
Фрик, Маркус; Гроэ, Мартин (2001), «Определение свойств первого порядка локально древовидно-разложимых структур», Журнал ACM , 48 (6): 1184–1206, arXiv : cs/0004007 , doi : 10.1145/504794.504798, MR 2143836, S2CID 999472.
Фомин, Федор В.; Локштанов, Даниэль; Саурабх, Сакет; Пилипчук, Михал; Врохна, Марчин (2018), «Полностью полиномиальные параметризованные вычисления для графов и матриц малой древовидной ширины», ACM Transactions on Algorithms , 14 (3): 34:1–34:45, arXiv : 1511.01379 , doi : 10.1145/3186898, S2CID 2144798.
Григорьев, Александр; Бодлендер, Ханс Л. (2007), «Алгоритмы для графов, встраиваемых с небольшим количеством пересечений на ребро», Algorithmica , 49 (1): 1–11, CiteSeerX 10.1.1.65.5071 , doi :10.1007/s00453-007-0010-x, MR 2344391, S2CID 8174422.
Халин, Рудольф (1976), « S -функции для графов», Журнал геометрии , 8 (1–2): 171–186, doi :10.1007/BF01917434, S2CID 120256194.
Као, Мин-Ян, ред. (2008), «Древовидная ширина графов», Энциклопедия алгоритмов, Springer, стр. 969, ISBN 9780387307701Еще одна давняя открытая проблема заключается в том, существует ли алгоритм с полиномиальным временем для вычисления ширины дерева планарных графов.
Корхонен, Туукка (2021), «Алгоритм 2-приближения с одним экспоненциальным временем для ширины дерева», Труды 62-го ежегодного симпозиума IEEE по основам компьютерной науки , IEEE, стр. 184–192, arXiv : 2104.07463 , doi : 10.1109/FOCS52979.2021.00026, ISBN 978-1-6654-2055-6, S2CID 233240958.
Лагергрен, Йенс (1993), «Верхняя граница размера препятствия», Теория структур графов (Сиэтл, Вашингтон, 1991) , Contemporary Mathematics, т. 147, Провиденс, Род-Айленд: Американское математическое общество, стр. 601–621, doi : 10.1090/conm/147/01202, ISBN 9780821851609, г-н 1224734.
Лагергрен, Йенс (1996), «Эффективные параллельные алгоритмы для графов ограниченной ширины дерева», Журнал алгоритмов , 20 (1): 20–44, doi :10.1006/jagm.1996.0002, MR 1368716.
Рамачандрамурти, Сиддхартхан (1997), «Структура и количество препятствий к древовидной ширине», SIAM Journal on Discrete Mathematics , 10 (1): 146–157, doi :10.1137/S0895480195280010, MR 1430552.
Рид, Брюс А. (1992), «Нахождение приблизительных разделителей и быстрое вычисление ширины дерева», в Kosaraju, S. Rao; Fellows, Mike; Wigderson, Avi; Ellis, John A. (ред.), Труды 24-го ежегодного симпозиума ACM по теории вычислений, 4-6 мая 1992 г., Виктория, Британская Колумбия, Канада , ACM, стр. 221–228, doi : 10.1145/129712.129734 , ISBN 0-89791-511-9, S2CID 16259988.
Робертсон, Нил ; Сеймур, Пол Д. (1984), «Миноры графа III: Ширина планарного дерева», Журнал комбинаторной теории , Серия B, 36 (1): 49–64, doi : 10.1016/0095-8956(84)90013-3.
Робертсон, Нил ; Сеймур, Пол Д. (1986), «Миноры графа V: Исключение планарного графа», Журнал комбинаторной теории , Серия B, 41 (1): 92–114, doi : 10.1016/0095-8956(86)90030-4.
Робертсон, Нил ; Сеймур, Пол Д. (1995), «Миноры графа XIII: проблема непересекающихся путей», Журнал комбинаторной теории , Серия B, 63 (1): 65–110, doi : 10.1006/jctb.1995.1006.
Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1994), «Быстрое исключение планарного графа», Журнал комбинаторной теории , Серия B, 62 (2): 323–348, doi : 10.1006/jctb.1994.1073 , MR 1305057.
Сатьянараяна, А.; Тунг, Л. (1990), «Характеристика частичных 3-деревьев», Networks , 20 (3): 299–322, doi :10.1002/net.3230200304, MR 1050503.
Сеймур, Пол Д.; Томас , Робин (1993), «Поиск графа и теорема о минимуме-максимуме для ширины дерева», Журнал комбинаторной теории , Серия B, 58 (1): 22–33, doi : 10.1006/jctb.1993.1027.
Шойхет, Кирилл; Гейгер, Дэн (1997), «Практический алгоритм поиска оптимальных триангуляций», в Кейперс, Бенджамин; Веббер, Бонни Л. (ред.), Труды Четырнадцатой национальной конференции по искусственному интеллекту и Девятой конференции по инновационным приложениям искусственного интеллекта, AAAI 97, IAAI 97, 27–31 июля 1997 г., Провиденс, Род-Айленд, США , AAAI Press / The MIT Press, стр. 185–190.
Торуп, Миккель (1998), «Все структурированные программы имеют небольшую ширину дерева и хорошее распределение регистров», Информация и вычисления , 142 (2): 159–181, doi : 10.1006/inco.1997.2697.
Корхонен, Туукка; Локштанов, Дэниел (2022), «Улучшенный параметризованный алгоритм для ширины дерева», arXiv : 2211.07154 [cs.DS].