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

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

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

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

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

Определение

Граф с восемью вершинами и его древовидное разложение на дерево с шестью узлами. Каждое ребро графа соединяет две вершины, которые перечислены вместе в некотором узле дерева, и каждая вершина графа указана в узлах смежного поддерева дерева. Каждый узел дерева содержит не более трех вершин, поэтому ширина этого разложения равна двум.

Древовидное разложение графа G = ( V , E ) — это дерево T с узлами X ₁ , …, X _n , где каждый X _i является подмножеством V , удовлетворяющим следующим свойствам (термин узел используется для обозначения вершины T, чтобы избежать путаницы с вершинами G ):

1. Объединение всех множеств X _i равно V . То есть каждая вершина графа содержится как минимум в одном узле дерева.
2. Если X _i и X _j содержат вершину v , то все узлы X _k из T на (уникальном) пути между X _i и X _j содержат вершину v также . Эквивалентно, узлы дерева, содержащие вершину v, образуют связное поддерево T .
3. Для каждого ребра ( 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 ) ⊆ β ( X ) всякий раз, когда X ⊆ Y. ,

Ежевика . четвертого порядка в сеточном графе 3×3, существование которой показывает, что граф имеет древовидную ширину не менее 3

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

Примеры

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

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

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

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

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

Плоские графы не имеют ограниченной ширины дерева, потому что n × n граф сетки представляет собой планарный граф с шириной дерева ровно n . Следовательно, если F — минорно-замкнутое семейство графов с ограниченной древовидной шириной, оно не может включать все планарные графы. И наоборот, если какой-то планарный граф не может быть минорным для графов семейства F , то существует константа k такая, что все графы в F имеют ширину дерева не более k . То есть следующие три условия эквивалентны друг другу:

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

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

Четыре запрещенных минора для дерева шириной 3: K ₅ (вверху слева), график октаэдра (внизу слева), граф Вагнера (вверху справа) и график пятиугольной призмы (внизу справа).

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

• Для k = 1 единственный запрещенный минор представляет собой граф циклов с 3 вершинами .
• Для k = 2 единственным запрещенным минором является 4-вершинный полный граф K ₄ .
• Для k = 3 существует четыре запрещенных минора: K ₅ , граф октаэдра , граф пятиугольной призмы и граф Вагнера . Из них два многогранных графа плоские.

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

Алгоритмы

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

NP-полно определить, имеет ли данный граф G ширину дерева не более заданной переменной k . Однако, когда k — любая фиксированная константа, графы с шириной дерева k можно распознать и ширины k за линейное время. построить для них разложение дерева Временная зависимость этого алгоритма от k является экспоненциальной.

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

Приближение	ж ( к )	г ( п )	ссылка
точный	О (1)	На ​ ​ к +2 )	Арнборг, Корней и Проскуровски (1987)
4 k + 3	О (3 3 тыс. )	На ​ ​ 2 )	Робертсон и Сеймур (1995)
8 тыс. + 7	2 О ( k журнал k )	н журнал 2 н	Лагергрен (1996)
5к ( 4 или 7к + +6 )	2 О ( k журнал k )	н войти н	Рид (1992)
точный	2 Хорошо ​ ​ 3 )	На ) ​ ​	Бодлендер (1996)
$O\left(k\cdot {\sqrt {\log k}}\right)$	О (1)	н О (1)	Файги, Хаджиагайи и Ли (2008)
4,5 тыс. + 4	2 3 тыс.	н 2	Амир (2010)
⁠ 11 / 3 ⁠ k + 4	2 3,6982 тыс.	н 3 бревно 4 н	Амир (2010)
точный	О (1)	О (1,7347 н )	Фомин, Тодинка и Вилланджер (2015)
3 тыс. + 2	2 Хорошо ​ ​ )	О ( нлогн n)	Бодлендер и др. (2016)
5 тыс. + 4	2 Хорошо ​ ​ )	На ) ​ ​	Бодлендер и др. (2016)
к 2	Хорошо ​ ​ 7 )	О ( нлогн n)	Fomin et al. (2018)
5 тыс. + 4	2 8.7658,765 тыс.	О ( нлогн n)	Бельбаси и Фюрер (2021a)
2к + 1	2 Хорошо ​ ​ )	На ) ​ ​	Корхонен (2021)
5 тыс. + 4	2 6,755 тыс.	О ( нлогн n)	Бельбаси и Фюрер (2021b)
точный	2 Хорошо ​ ​ 2 )	н 4	Корхонен и Локштанов (2022)
(1+ $\varepsilon$) к	к Хорошо ​ ​ / $\varepsilon$)	н 4	Корхонен и Локштанов (2022)

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

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

(еще нерешенные задачи по математике)

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

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

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

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

Доу и Корф улучшен алгоритм QuickBB с использованием поиска по принципу «сначала лучшее» . На некоторых графах этот алгоритм поиска по принципу «сначала лучший результат» на порядок быстрее, чем QuickBB.

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

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

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

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

Основная статья: теорема Курселя

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

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

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

$\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 ₁ , W ₂ , W ₃ представляют подмножества вершин, имеющих каждый из 3 цветов.Следовательно, согласно результатам Курселя, задача о 3-раскраске может быть решена за линейное время для графа с древовидным разложением ограниченной постоянной ширины дерева.

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

Ширина пути

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

Меньший размер сетки

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

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

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

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

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

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

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

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

Ссылки

• Амир, Эял (2010), «Алгоритмы аппроксимации ширины дерева», Algorithmica , 56 (4): 448–479, doi : 10.1007/s00453-008-9180-4 , MR   2581059 , S2CID   5874913 .
• Арнборг, С.; Корней, Д. ; Проскуровский А. (1987), "Сложность поиска вложений в $k$-дерево », SIAM Journal on Matrix Analysis and Applications , 8 (2): 277–284, doi : 10.1137/0608024 .
• Арнборг, Стефан; Проскуровский, Анджей; Корнейл, Дерек Г. (1990), «Запрещенные минорные характеристики частичных трехдеревьев», Discrete Mathematics , 80 (1): 1–19, doi : 10.1016/0012-365X(90)90292-P , MR   1045920 .
• Арнборг, С.; Проскуровски А. (1989), "Алгоритмы с линейным временем для NP-трудных задач, ограниченных частичным $k$-деревья », Дискретная прикладная математика , 23 (1):11–24, doi : 10.1016/0166-218X(89)90031-0 .
• Бельбаси, Махди; Фюрер, Мартин (2021a), «Улучшение приближения ширины дерева Рида», в Уэхаре, Рюхей; Хонг, Сокхи ; Нанди, Субхас К. (ред.), WALCOM: Алгоритмы и вычисления – 15-я Международная конференция и семинары, WALCOM 2021, Янгон, Мьянма, 28 февраля – 2 марта 2021 г., Материалы докладов , Конспекты лекций по информатике, том. 12635, Springer, стр. 166–181, arXiv : 2010.03105 , doi : 10.1007/978-3-030-68211-8_14 , MR   4239527 , S2CID   222177100 .
• Бельбаси, Махди; Фюрер, Мартин (2021b), «Нахождение всех крайних левых разделителей размера $\leq k$", в Ду, Дин-Чжу; Ду, Донглей; Ву, Чэньчэнь; Сюй, Дачуань (ред.), Комбинаторная оптимизация и приложения - 15-я Международная конференция, COCOA 2021, Тяньцзинь, Китай, 17-19 декабря 2021 г., Труды , Конспекты лекций по информатике, том 13135, Springer, стр. 273–287, arXiv : 2111.02614 , doi : 10.1007/978-3-030-92681-6_23 , S2CID   242758210.
• Берн, МВт; Лоулер, Эл . ; Вонг, AL (1987), «Вычисление оптимальных подграфов разложимых графов в линейном времени», Journal of Algorithms , 8 (2): 216–235, doi : 10.1016/0196-6774(87)90039-3 .
• Бертеле, Умберто; Бриоски, Франческо (1972), Непоследовательное динамическое программирование , Academic Press, стр. 37–38, ISBN  978-0-12-093450-8 .
• Бодлендер, Ханс Л. (1988), «Динамическое программирование на графах с ограниченной шириной дерева», Proc. 15-й Международный коллоквиум по автоматам, языкам и программированию , Конспекты лекций по информатике, том. 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 -дендрарий графов с ограниченной шириной дерева», Theoretical Computer Science , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228-4 .
• Бодлендер, Ганс Л.; Дрейндж, Пал Г.; Дреги, Маркус С.; Фомин Федор Владимирович; Локштанов Даниил; Пилипчук, Михал (2016), «А $c^{k}n$ Алгоритм 5-аппроксимации ширины дерева», SIAM Journal on Computing , 45 (2): 317–378, arXiv : 1304.6321 , doi : 10.1137/130947374 .
• Чекури, Чандра; Чужой, Юлия (2016), «Полиномиальные оценки для теоремы о минорной сетке», Журнал ACM , 63 (5): A40:1–65, arXiv : 1305.6577 , doi : 10.1145/2820609 , MR   3593966 , S2CID   209860422 .
• Курсель, Б. (1990), «Монадическая логика графов I второго порядка: распознаваемые множества конечных графов», Information and Computation , 85 : 12–75, CiteSeerX   10.1.1.158.5595 , doi : 10.1016/0890-5401 (90)90043-ч .
• Курсель, Б. (1992), «Монадическая логика второго порядка графов III: ширина дерева, запрещенные второстепенные элементы и проблемы сложности», Informatique Théorique (26): 257–286 .
• Демейн, Эрик Д .; Фомин Федор Владимирович; Хаджиагайи, Мохаммад Таги; Тиликос, Димитриос М. (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), «Краткое доказательство теоремы Халина о сетке», Статьи математического семинара Гамбургского университета , 74 : 237–242, doi : 10.1007/BF02941538 , MR   2112834 , S2CID   124603912 .
• Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN  978-3-540-26182-7 .
• Eppstein, D. (2000), «Диаметр и ширина дерева в семействах с меньшими графами», Algorithmica , 27 (3–4): 275–291, Arxiv : Math/9907126 , Doi : 31711600002020, MR 1759751, S2CID 3171160000 10.1007/S004530010020 , MR   1759751 , MR 1759751 , , S2CID   S2CID 3171160/ S004530010020. .
• Файги, Уриэль; Хаджиагайи, Мохаммад Таги; Ли, Джеймс Р. (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 в алгоритмах , 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 , МР   2344391 , S2CID   8174422 .
• Халин, Рудольф (1976), « S -функции для графов», Journal of Geometry , 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 , S2CID   233240958 .
• Лагергрен, Йенс (1993), «Верхняя граница размера препятствия», Теория структуры графов (Сиэтл, Вашингтон, 1991) , Contemporary Mathematics, vol. 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), «Нахождение приблизительных разделителей и быстрое вычисление ширины дерева», в Косараджу, С. Рао; Ребята, Майк; Вигдерсон, Ави; Эллис, Джон А. (ред.), Труды 24-го ежегодного симпозиума ACM по теории вычислений, 4–6 мая 1992 г., Виктория, Британская Колумбия, Канада , ACM, стр. 221–228, doi : 10.1145/129712.129734 , 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), «Характеристика частичных трехдеревьев», 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), «Все структурированные программы имеют небольшую ширину дерева и хорошее распределение регистров», Information and Computation , 142 (2): 159–181, doi : 10.1006/inco.1997.2697 .
• Корхонен, Туукка; Локштанов, Дэниел (2022), «Улучшенный параметризованный алгоритм определения ширины дерева», arXiv : 2211.07154 [ cs.DS ] .