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

Число, обозначающее близость графа к дереву.

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

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

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

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

Определение

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

Древовидная декомпозиция графа G = ( V , E ) — это дерево T с узлами X ₁ , …, X _n , где каждый X _i является подмножеством V , удовлетворяющим следующим свойствам ^[2] ( используется термин узел для ссылки на вершину 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 .

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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 }$

${\displaystyle \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-раскраске может быть решена за линейное время для графа с древовидным разложением ограниченной постоянной ширины дерева.

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

Ширина пути

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

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

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

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

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

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

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

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

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

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

Примечания

1. Дистель (2005), стр. 354–355.
2. Дистель (2005), раздел 12.3
3. Сеймур и Томас (1993).
4. Бодлендер (1998).
5. Торуп (1998).
6. Робертсон и Сеймур (1986).
7. Бодлендер (1988).
8. Арнборг, Проскуровски и Корнейл (1990); Сатьянараяна и Тунг (1990).
9. Рамачандрамурти (1997).
10. Лагергрен (1993).
11. Арнборг, Корней и Проскуровски (1987).
12. Бодлендер (1996).
13. Као (2008).
14. "Вибхав Гогате". Personal.utdallas.edu . Проверено 27 ноября 2022 г.
15. Gogate, Вибхав; Дектер, Рина (11 июля 2012 г.). «Полный алгоритм определения ширины дерева в любое время». arXiv : 1207.4109 [cs.DS].
16. «Лучший первый поиск по ширине дерева» . www.aaai.org . Проверено 27 ноября 2022 г.
17. Бертеле и Бриоски (1972).
18. Арнборг и Проскуровски (1989); Берн, Лоулер и Вонг (1987); Бодлендер (1988).
19. Курсель (1990); Курсель (1992)
20. Робертсон, Сеймур. Миноры графа. V. Исключение плоского графа . [1]
21. Чекури и Чужой (2016)
22. Демейн и Хаджиагайи (2008).
23. Дистель (2004).
24. Эппштейн (2000).
25. Эппштейн (2000); Демейн и Хаджиагайи (2004a).
26. Демейн и Хаджиагайи (2004b).
27. Демейн и др. (2004); Демейн и Хаджиагайи (2008).
28. Фрик и Гроэ (2001).
29. Григорьев и Бодлаендер (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 ${\displaystyle k}$.
• Арнборг, Стефан; Проскуровский, Анджей; Корнейл, Дерек Г. (1990), «Запрещенные минорные характеристики частичных трехдеревьев», Discrete Mathematics , 80 (1): 1–19, doi : 10.1016/0012-365X(90)90292-P , MR  1045920.
• Арнборг, С.; Проскуровски, А. (1989), «Алгоритмы с линейным временем для NP-трудных задач, ограниченных частичными -деревьями », Discrete Applied Mathematics , 23 (1): 11–24, doi : 10.1016/0166-218X(89)90031-0 ${\displaystyle k}$.
• Бельбаси, Махди; Фюрер, Мартин (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), «Нахождение всех крайних левых разделителей размера », в Ду, Дин-Чжу; Ду, Донглей; Ву, Ченчен; Сюй, Дачуань (ред.), Комбинаторная оптимизация и приложения - 15-я Международная конференция, COCOA 2021, Тяньцзинь, Китай, 17-19 декабря 2021 г., Труды , конспекты лекций по информатике, том. 13135, Springer, стр. 273–287, arXiv : 2111.02614 , doi : 10.1007/978-3-030-92681-6_23, S2CID  242758210 ${\displaystyle \leq k}$
• Берн, МВт; Лоулер, Эл . ; Вонг, А.Л. (1987), «Вычисление оптимальных подграфов разложимых графов в линейном времени», Журнал алгоритмов , 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), « Алгоритм с 5 приближениями для определения ширины дерева», SIAM Journal on Computing , 45 (2): 317–378, arXiv : 1304.6321 , doi : 10.1137/130947374 ${\displaystyle c^{k}n}$.
• Чекури, Чандра; Чужой, Юлия (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, S2 Идентификатор идентификатора  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 по алгоритмам , 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, номер документа : 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 / MIT Press, стр. 185–190..
• Торуп, Миккель (1998), «Все структурированные программы имеют небольшую ширину дерева и хорошее распределение регистров», Information and Computation , 142 (2): 159–181, doi : 10.1006/inco.1997.2697.
• Корхонен, Туукка; Локштанов, Дэниел (2022), «Улучшенный параметризованный алгоритм определения ширины дерева», arXiv : 2211.07154 [cs.DS].