Ширина пути

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

Ширина пути и декомпозиции пути тесно связаны с шириной дерева и декомпозицией дерева . Они играют ключевую роль в теории миноров графа : семейства графов, которые замкнуты относительно миноров графа и не включают все леса, могут быть охарактеризованы как имеющие ограниченную ширину пути, ^[2] а «вихри», появляющиеся в общей теории структур для семейств графов с замкнутыми минорами, имеют ограниченную ширину пути. ^[4] Ширина пути и графы с ограниченной шириной пути также имеют приложения в проектировании СБИС , рисовании графов и вычислительной лингвистике .

NP -трудно найти ширину пути произвольных графов или даже точно ее приблизить. ^[5]^[6] Однако эта задача поддается решению с фиксированными параметрами : проверка того, имеет ли граф ширину пути $k$ , может быть решена за время, линейно зависящее от размера графа, но сверхэкспоненциально от $k$ . ^[7] Кроме того, для нескольких специальных классов графов, таких как деревья , ширину пути можно вычислить за полиномиальное время независимо от $k$ . ^[8]^[9] Многие задачи в графовых алгоритмах можно эффективно решить на графах с ограниченной шириной пути, используя динамическое программирование для декомпозиции пути графа. ^[10] Декомпозиция пути также может использоваться для измерения пространственной сложности алгоритмов динамического программирования на графах с ограниченной шириной дерева . ^[11]

Определение

Пример графа $G$ с шириной пути 2 и его разложением пути ширины 2. Нижняя часть изображения представляет собой тот же граф и разложение пути с добавлением цвета для выделения. (Этот пример является адаптацией графа, представленного в работе Bodlaender (1994a), выделение добавлено)

В первой из своей знаменитой серии статей о минорах графов Нил Робертсон и Пол Сеймур (1983) определяют путевую декомпозицию графа $G$ как последовательность подмножеств $X i$ вершин графа $G$ с двумя свойствами:

Для каждого ребра $G$ существует $i$ такое, что обе конечные точки ребра принадлежат подмножеству $X i$ , и
Для каждых трех индексов $i \leq j \leq k$ , $X_{i}\cap X_{k}\subseteq X_{j}.$

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

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

Альтернативные характеристики

Как описывает Бодлендер (1998), ширину пути можно охарактеризовать многими эквивалентными способами.

Последовательности склеивания

Путевое разложение можно описать как последовательность графов $G i$ , которые склеиваются путем идентификации пар вершин из последовательных графов в последовательности, так что результатом выполнения всех этих склеиваний является $G$ . Графы $G i$ можно рассматривать как индуцированные подграфы множеств $X i$ в первом определении путевых разложений, при этом две вершины в последовательных индуцированных подграфах склеиваются, когда они индуцированы одной и той же вершиной в $G$ , а в другом направлении можно восстановить множества $X i$ как множества вершин графов $G i$ . Ширина путевого разложения тогда на единицу меньше максимального числа вершин в одном из графов $G i$ . ^[2]

Толщина интервала

Ширина пути любого графа $G$ на единицу меньше наименьшего числа клик интервального графа , содержащего $G$ в качестве подграфа. ^[12] То есть для каждого разложения пути графа $G$ можно найти интервальный суперграф $G$ , а для каждого интервального суперграфа $G$ можно найти разложение пути графа $G$ , такое, что ширина разложения на единицу меньше числа клик интервального графа.

В одном направлении предположим, что задано разложение пути $G.$ Тогда можно представить узлы разложения как точки на линии (в порядке пути) и представить каждую вершину $v$ как замкнутый интервал, имеющий эти точки в качестве конечных точек. Таким образом, узлы разложения пути, содержащие $v,$ соответствуют репрезентативным точкам в интервале для $v$ . Граф пересечений интервалов, образованных из вершин $G,$ является интервальным графом, который содержит $G$ как подграф. Его максимальные клики задаются наборами интервалов, содержащих репрезентативные точки, а его максимальный размер клики равен единице плюс ширина пути $G$ .

В другом направлении, если $G$ является подграфом интервального графа с кликовым числом $p + 1$ , то $G$ имеет путевое разложение ширины $p$ , узлы которого задаются максимальными кликами интервального графа. Например, интервальный граф, показанный с его интервальным представлением на рисунке, имеет путевое разложение с пятью узлами, соответствующими его пяти максимальным кликам $ABC$ , $ACD$ , $CDE$ , $CDF$ и $FG$ ; максимальный размер клики равен трем, а ширина этого путевого разложения равна двум.

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

Число разделений вершин

Числом разделения вершин графа $G$ относительно линейного порядка вершин графа $G$ является наименьшее число $s$ такое, что для каждой вершины $v$ не более $s$ вершин находятся раньше $v$ в порядке, но имеют $v$ или более позднюю вершину в качестве соседа. Числом разделения вершин графа $G$ является наименьшее числом разделения вершин графа $G$ относительно любого линейного порядка графа $G.$ Число разделения вершин было определено Эллисом, Садборо и Тернером (1983) и равно ширине пути графа $G.$ ^[13] Это следует из более ранней эквивалентности с числами клик интервального графа: если $G$ является подграфом интервального графа $I$ , представленным (как на рисунке) таким образом, что все конечные точки интервала различны, то упорядочение левых конечных точек интервалов графа $I$ имеет число разделения вершин на единицу меньше числа клики графа $I.$ И в другом направлении, из линейного упорядочения $G$ можно вывести интервальное представление, в котором левая конечная точка интервала для вершины $v$ является ее позицией в упорядочении, а правая конечная точка является позицией соседа $v,$ который находится последним в упорядочении.

Номер поиска узла

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

Границы

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

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

Любой $n$ -вершинный лес имеет ширину пути $O (log n)$ . ^[17] Ведь в лесу всегда можно найти постоянное число вершин, удаление которых оставляет лес, который можно разбить на два меньших подлеска с не более чем $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}2 n ⁄ 3$ вершинами каждый. Линейное расположение, образованное рекурсивным разбиением каждого из этих двух подлесков, помещая разделяющие вершины между ними, имеет логарифмическое число поиска вершин. Тот же метод, примененный к древовидной декомпозиции графа, показывает, что если ширина дерева $n$ -вершинного графа $G$ равна $t$ , то ширина пути $G$ равна $O (t log n)$ . ^[18] Поскольку внешнепланарные графы , последовательно-параллельные графы и графы Халина имеют ограниченную ширину дерева, все они также имеют не более логарифмическую ширину пути.

Как и его отношения к древовидной ширине, ширина пути также связана с шириной клики и шириной разреза через линейные графы ; линейный граф $L (G)$ графа $G$ имеет вершину для каждого ребра $G$ , и две вершины в $L (G)$ являются смежными, когда соответствующие два ребра $G$ имеют общую конечную точку. Любое семейство графов имеет ограниченную ширину пути тогда и только тогда, когда его линейные графы имеют ограниченную линейную ширину клики, где линейная ширина клики заменяет операцию непересекающегося объединения из ширины клики на операцию присоединения одной новой вершины. ^[19] Если связный граф с тремя или более вершинами имеет максимальную степень три, то его ширина разреза равна числу разделения вершин его линейного графа. ^[20]

В любом плоском графе ширина пути не более чем пропорциональна квадратному корню из числа вершин. ^[21] Один из способов найти декомпозицию пути с такой шириной (аналогично логарифмической ширине декомпозиции пути лесов, описанной выше) — использовать теорему о плоском разделителе для нахождения набора из $O (\sqrt n)$ вершин, удаление которых разделяет граф на два подграфа, каждый из которых содержит не более $2$ $n$ $⁄$ $3$ вершин, и объединить рекурсивно построенные декомпозиции пути для каждого из этих двух подграфов. Тот же метод применим к любому классу графов, для которых справедлива аналогичная теорема о разделителе. ^[22] Поскольку, подобно планарным графам, графы в любом фиксированном семействе минорно-замкнутых графов имеют сепараторы размера $O$ $($ $\sqrt$ $n$ $)$ , ^[23] отсюда следует, что путевая ширина графов в любом фиксированном семействе минорно-замкнутых графов снова равна $O$ $($ $\sqrt$ $n$ $)$ . Для некоторых классов планарных графов путевая ширина графа и путевая ширина его дуального графа должны находиться в пределах постоянного множителя друг от друга: границы такого вида известны для двусвязных внешнепланарных графов ^[24] и для полиэдральных графов. ^[25] Для 2-связных планарных графов путевая ширина дуального графа меньше путевой ширины линейного графа. ^[26] Остается открытым вопрос, всегда ли путевая ширина планарного графа и его дуального графа находятся в пределах постоянного множителя друг от друга в остальных случаях.

В некоторых классах графов было доказано, что ширина пути и ширина дерева всегда равны друг другу: это справедливо для кографов, [27] графов перестановок, [28] дополнений графов сравнимости ^, [ 29 ^] и графов сравнимости интервальных ^{порядков} . [ 30 ^]

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

Какова наибольшая возможная ширина пути кубического графа

с n

вершинами ?

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

В любом кубическом графе , или, более общо, в любом графе с максимальной степенью вершины три, ширина пути не превышает $n$ $⁄$ $6$ $+ o($ $n$ $)$ , где $n$ — число вершин в графе. Существуют кубические графы с шириной пути $0,082$ $n$ , но неизвестно, как сократить этот разрыв между этой нижней границей и верхней границей $n$ $⁄$ $6.$ ^[31]

Вычисление путей-декомпозиций

NP-полной задачей является определение того, является ли ширина пути заданного графа не более $k$ , когда $k$ — переменная, заданная как часть входных данных. ^[5] Наиболее известные наихудшие временные границы для вычисления ширины пути произвольных $n$ -вершинных графов имеют вид $O (2 n n c)$ для некоторой константы $c$ . ^[32] Тем не менее, известно, что несколько алгоритмов вычисляют декомпозиции путей более эффективно, когда ширина пути мала, когда класс входных графов ограничен или приблизительно.

Возможность обработки с фиксированными параметрами

Ширина пути является фиксированно-параметрически трактуемой : для любой константы $k$ можно проверить, является ли ширина пути не более $k$ , и если это так, найти декомпозицию пути ширины $k$ за линейное время. ^[7] В общем, эти алгоритмы работают в два этапа. На первом этапе предположение, что граф имеет ширину пути $k,$ используется для поиска декомпозиции пути или декомпозиции дерева, которая не является оптимальной, но ширина которой может быть ограничена как функция $k$ . На втором этапе к этой декомпозиции применяется алгоритм динамического программирования , чтобы найти оптимальную декомпозицию. Однако временные ограничения для известных алгоритмов этого типа являются экспоненциальными по $k 2$ , непрактичными, за исключением наименьших значений $k$ . ^[33] Для случая $k = 2$ явный алгоритм линейного времени, основанный на структурной декомпозиции графов ширины пути-2, дан де Флюйтером (1997).

Специальные классы графов

Bodlaender (1994) рассматривает сложность вычисления ширины пути на различных специальных классах графов. Определение того, является ли ширина пути графа $G$ не более $k,$ остается NP-полным, когда $G$ ограничивается графами ограниченной степени, ^[34] планарными графами , ^[34] планарными графами ограниченной степени, ^[34] хордовыми графами , ^[35] хордовыми домино, ^[36] дополнениями графов сравнимости , [ ^29] и двудольными дистанционно-наследственными графами . ^{[37] Из этого немедленно следует, что это также NP-полное для семейств графов, которые содержат двудольные дистанционно-наследственные графы, включая двудольные}графы , хордальные двудольные графы, дистанционно-наследственные графы и круговые графы . ^[37]

Однако ширина пути может быть вычислена за линейное время для деревьев и лесов. ^[9] Она также может быть вычислена за полиномиальное время для графов с ограниченной шириной дерева, включая последовательно-параллельные графы , внешнепланарные графы и графы Халина , ^[7] , а также для расщепленных графов , ^[38] для дополнений хордовых графов, ^[39] для графов перестановок , ^[28] для кографов , ^[27] для графов дуг окружности , ^[40] для графов сравнимости интервальных порядков, ^[30] и, конечно, для самих интервальных графов , поскольку в этом случае ширина пути всего на единицу меньше максимального числа интервалов, покрывающих любую точку в интервальном представлении графа.

Алгоритмы аппроксимации

Аппроксимировать ширину пути графа с точностью до аддитивной константы — задача NP-трудная. ^[6] Лучший известный коэффициент аппроксимации полиномиального алгоритма аппроксимации ширины пути — $O ((log n) 3/2)$ . ^[41] Более ранние алгоритмы аппроксимации ширины пути см. в работах Bodlaender et al. (1992) и Guha (2000). Аппроксимации для ограниченных классов графов см. в работе Kloks & Bodlaender (1992).

Графические несовершеннолетние

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

За исключением леса

Если семейство графов $F$ замкнуто относительно взятия миноров (каждый минор члена $F$ также находится в $F$ ), то по теореме Робертсона–Сеймура $F$ можно охарактеризовать как графы, которые не имеют ни одного минора в $X$ , где $X$ — конечное множество запрещенных миноров . ^[42] Например, теорема Вагнера утверждает, что планарные графы — это графы, которые не имеют ни полного графа $K 5$ , ни полного двудольного графа $K 3,3$ в качестве миноров. Во многих случаях свойства $F$ и свойства $X$ тесно связаны, и первый такой результат такого типа был получен Робертсоном и Сеймуром (1983), ^[2] и связывает ограниченную путевую ширину с существованием леса в семействе запрещенных миноров. В частности, определим семейство графов $F как имеющее$ ограниченную путевую ширину , если существует константа $p$ такая, что каждый граф в $F$ имеет путевую ширину не более $p$ . Тогда замкнутое по минорам семейство $F$ имеет ограниченную ширину пути тогда и только тогда, когда множество $X$ запрещенных миноров для $F$ включает в себя хотя бы один лес.

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

Препятствия к ограничению ширины пути

Свойство иметь ширину пути не более $p$ само по себе закрыто относительно взятия миноров: если $G$ имеет разложение пути с шириной не более $p$ , то то же самое разложение пути остается действительным, если любое ребро удалено из $G$ , и любая вершина может быть удалена из $G$ и из его разложения пути без увеличения ширины. Сокращение ребра также может быть выполнено без увеличения ширины разложения путем слияния подпутей, представляющих две конечные точки сжатого ребра. Следовательно, графы ширины пути не более $p$ могут быть охарактеризованы множеством $X p$ исключенных миноров. ^[42]^[44]

Хотя $X p$ обязательно включает в себя по крайней мере один лес, неверно, что все графы в $X p$ являются лесами: например, $X 1$ состоит из двух графов, дерева с семью вершинами и треугольника $K 3$ . Однако множество деревьев в $X p$ можно точно охарактеризовать: эти деревья являются в точности теми деревьями, которые могут быть образованы из трех деревьев в $X p - 1$ путем соединения новой корневой вершины ребром с произвольно выбранной вершиной в каждом из трех меньших деревьев. Например, дерево с семью вершинами в $X 1$ образовано таким образом из дерева с двумя вершинами (одним ребром) в $X 0$ . Основываясь на этой конструкции, можно показать, что число запрещенных миноров в $X p$ $составляет по крайней мере (p!) 2$ . ^[44] Был вычислен полный набор $X 2$ запрещенных миноров для графов с шириной пути 2; он содержит 110 различных графов. ^[45]

Теория структуры

Теорема о структуре графа для семейств графов с замкнутыми минорами утверждает, что для любого такого семейства $F$ графы в $F$ могут быть разложены на кликовые суммы графов, которые могут быть вложены в поверхности ограниченного рода , вместе с ограниченным числом вершин и вихрей для каждого компонента кликовой суммы. Вершина — это вершина, которая может быть смежной с любой другой вершиной в своем компоненте, в то время как вихрь — это граф с ограниченной шириной пути, который вклеен в одну из граней вложения компонента с ограниченным родом. Циклическое упорядочение вершин вокруг грани, в которую вложен вихрь, должно быть совместимо с разложением пути вихря, в том смысле, что разрыв цикла для формирования линейного порядка должен приводить к порядку с ограниченным числом разделения вершин. ^[4] Эта теория, в которой ширина пути тесно связана с произвольными семействами графов с замкнутыми минорами, имеет важные алгоритмические приложения. ^[46]

Приложения

СБИС

При проектировании СБИС проблема разделения вершин изначально изучалась как способ разбиения схем на более мелкие подсистемы с небольшим количеством компонентов на границе между подсистемами. ^[34]

Ohtsuki et al. (1979) используют толщину интервала для моделирования количества дорожек, необходимых в одномерной компоновке схемы VLSI, образованной набором модулей, которые должны быть соединены системой сетей. В их модели формируется граф, в котором вершины представляют сети, и в котором две вершины соединены ребром, если их сети обе подключаются к одному и тому же модулю; то есть, если модули и сети интерпретируются как формирующие узлы и гиперребра гиперграфа, то граф, образованный из них, является его линейным графом . Интервальное представление суперграфа этого линейного графа вместе с раскраской суперграфа описывает расположение сетей вдоль системы горизонтальных дорожек (одна дорожка на цвет) таким образом, что модули могут быть размещены вдоль дорожек в линейном порядке и подключены к соответствующим сетям. Тот факт, что интервальные графы являются идеальными графами ^[47], подразумевает, что количество цветов, необходимых в оптимальном расположении этого типа, совпадает с числом клик интервального завершения сетевого графа.

Макет матрицы вентилей ^[48] — это особый стиль макета КМОП СБИС для булевых логических схем. В макетах матрицы вентилей сигналы распространяются вдоль «линий» (вертикальных сегментов линий), в то время как каждый вентиль схемы формируется последовательностью функций устройства, которые лежат вдоль горизонтального сегмента линий. Таким образом, горизонтальный сегмент линии для каждого вентиля должен пересекать вертикальные сегменты для каждой из линий, которые формируют входы или выходы вентиля. Как и в макетах Оцуки и др. (1979), макет этого типа, который минимизирует количество вертикальных дорожек, на которых должны быть расположены линии, может быть найден путем вычисления ширины пути графа, в котором линии являются его вершинами, а пары линий, разделяющие вентиль, являются его ребрами. ^[49] Тот же алгоритмический подход можно использовать и для моделирования задач сворачивания в программируемых логических массивах . ^[50]

Графическое изображение

Ширина пути имеет несколько применений для построения графиков :

Минимальные графы, имеющие заданное число пересечений , имеют ширину пути, ограниченную функцией их числа пересечений. ^[51]
Число параллельных линий, на которых вершины дерева могут быть нарисованы без пересечения ребер (при различных естественных ограничениях на способы размещения смежных вершин относительно последовательности линий), пропорционально ширине пути дерева. ^[52]
Рисунок k -пересечения h -слоя графа G — это размещение вершин G на h различных горизонтальных линиях с ребрами, проложенными как монотонные многоугольные пути между этими линиями, таким образом, что существует не более k пересечений. Графы с такими рисунками имеют ширину пути, которая ограничена функцией h и k . Поэтому, когда h и k оба постоянны, можно за линейное время определить, имеет ли граф рисунок k -пересечения h -слоя. ^[53]
Граф с n вершинами и шириной пути p может быть вложен в трехмерную сетку размера p × p × n таким образом, что никакие два ребра (представленные как отрезки прямых линий между точками сетки) не пересекаются друг с другом. Таким образом, графы с ограниченной шириной пути имеют вложения этого типа с линейным объемом. ^[54]

Проектирование компилятора

При компиляции языков программирования высокого уровня ширина пути возникает в проблеме переупорядочения последовательностей прямолинейного кода (то есть кода без ветвей или циклов потока управления ) таким образом, чтобы все значения, вычисленные в коде, можно было поместить в регистры машины вместо того, чтобы выгружать их в основную память. В этом приложении код, который должен быть скомпилирован, представляется в виде направленного ациклического графа , в котором узлы представляют входные значения для кода и значения, вычисленные операциями внутри кода. Ребро от узла x до узла y в этом DAG представляет тот факт, что значение x является одним из входов для операции y . Топологическое упорядочение вершин этого DAG представляет допустимое переупорядочение кода, а количество регистров, необходимых для вычисления кода в данном порядке, задается числом разделения вершин порядка. ^[55]

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

Лингвистика

Корнаи и Туза (1992) описывают применение ширины пути в обработке естественного языка . В этом приложении предложения моделируются как графы, в которых вершины представляют слова, а ребра представляют отношения между словами; например, если прилагательное изменяет существительное в предложении, то граф будет иметь ребро между этими двумя словами. Из-за ограниченной емкости кратковременной памяти человека ^[56] Корнаи и Туза утверждают, что этот граф должен иметь ограниченную ширину пути (точнее, они утверждают, ширину пути не более шести), иначе люди не смогли бы правильно анализировать речь.

Экспоненциальные алгоритмы

Многие проблемы в графовых алгоритмах могут быть эффективно решены на графах с низкой шириной пути, используя динамическое программирование для декомпозиции пути графа. ^[10] Например, если задано линейное упорядочение вершин n -вершинного графа G с числом разделения вершин w , то можно найти максимальное независимое множество G за время O(2 ^w n ). ^[31] На графах с ограниченной шириной пути этот подход приводит к фиксированно-параметрическим разрешимым алгоритмам, параметризованным шириной пути. ^[49] Такие результаты нечасто встречаются в литературе, поскольку они включаются в аналогичные алгоритмы, параметризованные шириной дерева; однако ширина пути возникает даже в алгоритмах динамического программирования на основе ширины дерева при измерении пространственной сложности этих алгоритмов. ^[11]

Тот же метод динамического программирования может быть применен к графам с неограниченной шириной пути, что приводит к алгоритмам, которые решают непараметризованные графовые задачи за экспоненциальное время . Например, объединение этого подхода динамического программирования с тем фактом, что кубические графы имеют ширину пути n /6 + o( n ) показывает, что в кубическом графе максимальное независимое множество может быть построено за время O(2 ^{n /6 + o( n )} ), быстрее, чем предыдущие известные методы. ^[31] Похожий подход приводит к улучшенным алгоритмам экспоненциального времени для задач максимального разреза и минимального доминирующего множества в кубических графах, ^[31] и для нескольких других NP-трудных задач оптимизации. ^[57]

Смотрите также

Боксичность , другой способ измерения сложности произвольного графа в терминах интервальных графов
Ширина разреза — минимально возможная ширина линейного порядка вершин графа.
Глубина дерева — число, которое ограничено для семейства минорно-замкнутых графов тогда и только тогда, когда семейство исключает путь
Вырожденность — мера разреженности графа, которая не превышает ширины его пути.
Пропускная способность графа , другая NP-полная задача оптимизации, включающая линейные макеты графов.
Число Стралера , мера сложности корневых деревьев, определяемая аналогично ширине пути некорневых деревьев.

Примечания

^ Дистель и Кюн (2005).
^ abcd Робертсон и Сеймур (1983).
^ Киннерсли (1989); Бодлендер (1998).
^ Робертсон и Сеймур (2003).
^ ab Кашивабара и Фудзисава (1979); Оцуки и др. (1979); Ленгауэр (1981); Арнборг, Корнейл и Проскуровски (1987).
^ аб Бодлендер и др. (1992).
^ abc Bodlaender (1996); Bodlaender & Kloks (1996)
^ Бодлендер (1994).
^ Аб Мёринг (1990); Шеффлер (1990); Эллис, Садборо и Тернер (1994); Пэн и др. (1998); Скодинис (2000); Скодинис (2003 г.); Кудерт, Хук и Мазаурик (2012).
^ ab Арнборг (1985).
^ ab Aspvall, Proskurowski & Telle (2000).
^ Бодлендер (1998), Теорема 29, стр. 13.
^ Кинерсли (1989); Кинерсли (1992); Бодлендер (1998), Теорема 51.
^ Проскуровски и Телле (1999).
^ Корах и Солель (1993), Лемма 3, стр. 99; Бодлендер (1998), Теорема 47, стр. 24.
^ Корах и Солель (1993), Лемма 1, стр. 99; Бодлендер (1998), Теорема 49, стр. 24.
^ Корах и Солель (1993), Теорема 5, стр. 99; Бодлендер (1998), Теорема 66, стр. 30. Шеффлер (1992) дает более точную верхнюю границу $log 3 (2 n + 1)$ для ширины пути $n$ -вершинного леса.
^ Корах и Солель (1993), Теорема 6, стр. 100; Бодлендер (1998), Следствие 24, стр. 10.
^ Гурски и Ванке (2007).
^ Головач (1993).
^ Бодлендер (1998), Следствие 23, стр. 10.
^ Бодлендер (1998), Теорема 20, стр. 9.
^ Алон, Сеймур и Томас (1990).
^ Бодлендер и Фомин (2002); Кудерт, Хук и Серени (2007).
^ Фомин и Тиликос (2007); Амини, Юк и Перен (2009).
^ Фомин (2003).
^ аб Бодлендер и Меринг (1990).
^ аб Бодлендер, Клокс и Кратч (1993).
^ ab Хабиб и Мёринг (1994).
^ ab Garbe (1995).
^ abcd Фомин и Хёйе (2006).
^ Фомин и др. (2008).
^ Дауни и Феллоуз (1999), стр.12.
^ abcd Monien & Sudborough (1988).
^ Густедт (1993).
^ Клокс, Кратч и Мюллер (1995). Хордовое домино — это хордовый граф, в котором каждая вершина принадлежит не более чем двум максимальным кликам.
^ ab Клокс и др. (1993).
^ Клокс и Бодлендер (1992); Густедт (1993).
^ Гарбе (1995) приписывает этот результат докторской диссертации Тона Клокса 1993 года; полиномиальный алгоритм Гарбе для графов сравнимости интервальных порядков обобщает этот результат, поскольку любой хордовый граф должен быть графом сравнимости этого типа.
^ Сучан и Тодинка (2007).
^ Файги, Хаджиагайи и Ли (2005).
^ Робертсон и Сеймур (2004).
^ Бьенсток и др. (1991); Дистель (1995); Кэттелл, Диннин и Феллоуз (1996).
^ Аб Кинерсли (1992); Такахаши, Уэно и Кадзитани (1994); Бодлендер (1998), с. 8.
^ Киннерсли и Лэнгстон (1994).
^ Демейн, Хаджиагайи и Каварабаяши (2005).
^ Берге (1967).
^ Лопес и Лоу (1980).
^ ab Fellows & Langston (1989).
^ Меринг (1990); Феррейра и Сонг (1992).
^ Глинены (2003).
^ Судерман (2004).
^ Дуймович и др. (2008).
^ Дуймович, Морин и Вуд (2003).
^ аб Бодлендер, Густедт и Телле (1998).
^ Миллер (1956).
^ Кнейс и др. (2005); Бьорклунд и Хусфельдт (2008).

Ссылки

Алон, Нога ; Сеймур, Пол ; Томас, Робин (1990), «Теорема о разделителе для графов с исключенным минором и ее приложения», Труды 22-го симпозиума ACM по теории вычислений (STOC 1990) , стр. 293–299, doi : 10.1145/100216.100254 , ISBN 0897913612, S2CID 17521329.
Амини, Омид; Хук, Флориан; Перенн, Стефан (2009), «О ширине пути плоских графов», SIAM Journal on Discrete Mathematics , 23 (3): 1311–1316, doi : 10.1137/060670146.
Арнборг, Стефан (1985), «Эффективные алгоритмы для комбинаторных задач на графах с ограниченной разложимостью – Обзор», BIT , 25 (1): 2–23, doi :10.1007/BF01934985, S2CID 122263659.
Арнборг, Стефан; Корнейл, Дерек Г.; Проскуровски, Анджей (1987), «Сложность поиска вложений в $k$ -дерево», Журнал SIAM по алгебраическим и дискретным методам , 8 (2): 277–284, doi :10.1137/0608024.
Аспвалл, Бенгт; Проскуровски, Анджей; Телле, Ян Арне (2000), «Требования к памяти для табличных вычислений в алгоритмах частичного k -дерева», Algorithmica , 27 (3): 382–394, doi :10.1007/s004530010025, S2CID 9690525.
Берж, Клод (1967), «Некоторые классы совершенных графов», Теория графов и теоретическая физика , Нью-Йорк: Academic Press, стр. 155–165.
Бьенсток, Дэн; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1991), «Быстрое исключение леса», Журнал комбинаторной теории, Серия B , 52 (2): 274–283, doi : 10.1016/0095-8956(91)90068-U.
Бьёрклунд, Андреас; Хусфельдт, Торе (2008), «Точные алгоритмы для точной выполнимости и количества идеальных совпадений», Algorithmica , 52 (2): 226–249, doi :10.1007/s00453-007-9149-8, S2CID 37693881.
Bodlaender, Hans L. (1994), «Туристический путеводитель по древовидной ширине», в Dassow, Jürgen; Kelemenová, Alisa (ред.), Developments in Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 November 1992) , Topics in Computer Mathematics, т. 6, Gordon and Breach, стр. 1–20.
Бодлендер, Ханс Л. (1994a), «Туристический путеводитель по древовидности», Acta Cybernetica , 11 : 1–2
Бодлендер, Ханс Л. (1996), «Линейный алгоритм для поиска древовидных декомпозиций малой ширины», SIAM Journal on Computing , 25 (6): 1305–1317, doi : 10.1137/S0097539793251219, hdl : 1874/16670.
Бодлендер, Ханс Л. (1998), «Частичный k -дендрарий графов с ограниченной древовидной шириной», Теоретическая информатика , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228-4.
Бодлендер, Ханс Л.; Фомин, Федор В. (2002), «Аппроксимация ширины пути внешнепланарных графов», Журнал алгоритмов , 43 (2): 190–200, doi :10.1016/S0196-6774(02)00001-9.
Bodlaender, Hans L .; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1992), "Approximating treewidth, pathwidth, and minimum exception tree height", Графовые теоретические концепции в информатике , Lecture Notes in Computer Science , т. 570, стр. 1–12, doi : 10.1007/3-540-55121-2_1, hdl : 1874/17927 , ISBN 978-3-540-55121-8.
Бодлендер, Ханс Л.; Густедт, Йенс; Телле, Ян Арне (1998), «Распределение регистров с линейной скоростью для фиксированного числа регистров», Труды 9-го симпозиума ACM–SIAM по дискретным алгоритмам (SODA '98) (PDF) , стр. 574–583.
Бодлендер, Ханс Л.; Клокс, Тон (1996), «Эффективные и конструктивные алгоритмы для ширины пути и древовидной ширины графов», Журнал алгоритмов , 21 (2): 358–402, doi : 10.1006/jagm.1996.0049, hdl : 1874/16538.
Bodlaender, Hans L .; Kloks, Ton; Kratsch, Dieter (1993), "Ширина дерева и ширина пути графов перестановок", Proc. 20th International Colloquium on Automata, Languages and Programming (ICALP 1993) , Lecture Notes in Computer Science, vol. 700, Springer-Verlag, pp. 114–125, doi : 10.1007/3-540-56939-1_66, hdl : 1874/16657 , ISBN 978-3-540-56939-8.
Bodlaender, Hans L. ; Möhring, Rolf H. (1990), "The pathwidth and treewidth of cographs", Proc. 2nd Scandinavian Workshop on Algorithm Theory , Lecture Notes in Computer Science, vol. 447, Springer-Verlag, pp. 301–309, doi :10.1007/3-540-52846-6_99, hdl : 1874/16625 , ISBN 978-3-540-52846-3.
Кеттелл, Кевин; Диннин, Майкл Дж.; Феллоуз, Майкл Р. (1996), «Простой алгоритм линейного времени для поиска декомпозиций путей малой ширины», Information Processing Letters , 57 (4): 197–203, arXiv : math/9410211 , doi : 10.1016/0020-0190(95)00190-5, S2CID 2442557.
Кудерт, Дэвид; Хак, Флориан; Мазаурик, Дориан (2012), «Распределенный алгоритм вычисления числа поиска узлов в деревьях» (PDF) , Algorithmica , 63 (1): 158–190, doi :10.1007/s00453-011-9524-3.
Кудерт, Дэвид; Хук, Флориан; Серени, Жан-Себастьян (2007), «Ширина пути внешнепланарных графов» (PDF) , Journal of Graph Theory , 55 (1): 27–41, doi : 10.1002/jgt.20218.
Дистель, Рейнхард (1995), «Миноры графа I: краткое доказательство теоремы о ширине пути», Комбинаторика, вероятность и вычисления , 4 (1): 27–30, doi :10.1017/S0963548300001450.
Дистель, Рейнхард; Кюн, Даниэла (2005), «Младшие иерархии графов», Дискретная прикладная математика , 145 (2): 167–182, doi : 10.1016/j.dam.2004.01.010.
Демейн, Эрик Д.; Хаджиагайи , МохаммадТаги ; Каварабаяши, Кен-ичи (2005), «Теория алгоритмических графовых миноров: декомпозиция, аппроксимация и раскраска», Труды 46-го симпозиума IEEE по основам компьютерной науки (FOCS 2005) , стр. 637–646, doi :10.1109/SFCS.2005.14, ISBN 0-7695-2468-0, S2CID 13238254.
Дауни, Род Г.; Феллоуз , Майкл Р. (1999), Параметризованная сложность , Springer-Verlag, ISBN 0-387-94883-X.
Дуймович, В .; Феллоуз, М.Р .; Китчинг, М.; Лиотта, Г.; Маккартин, К.; Нишимура, Н.; Рэгде, П.; Розамонд, Ф.; Уайтсайдс, С .; Вуд, Дэвид Р. (2008), «О параметризованной сложности рисования многослойных графов», Algorithmica , 52 (2): 267–292, doi :10.1007/s00453-007-9151-1, S2CID 2298634.
Дуймович, Вида ; Морин, Пат ; Вуд, Дэвид Р. (2003), «Ширина пути и трехмерные прямолинейные сетчатые рисунки графов» (PDF) , Труды 10-го Международного симпозиума по рисованию графов (GD 2002) , Конспект лекций по информатике, том 2528, Springer-Verlag, стр. 42–53.
Эллис, JA; Садборо, IH; Тернер, JS (1983), "Разделение графа и число поиска", Труды конференции Allerton 1983 года по коммуникациям, управлению и вычислениям. Как цитируют Мониен и Садборо (1988).
Эллис, JA; Садборо, IH; Тернер, JS (1994), «Разделение вершин и число поиска дерева», Информация и вычисления , 113 (1): 50–79, doi : 10.1006/inco.1994.1064.
Файге, Уриэль ; Хаджиагайи, Мохаммадтаги ; Ли, Джеймс Р. (2005), «Улучшенные алгоритмы аппроксимации для разделителей вершин с минимальным весом», Труды 37-го симпозиума ACM по теории вычислений (STOC 2005) , стр. 563–572, doi :10.1145/1060590.1060674, ISBN 1581139608, S2CID 14097859.
Fellows, Michael R .; Langston, Michael A. (1989), «О поисковых решениях и эффективности алгоритмов с полиномиальным временем», Proc. 21st ACM Symposium on Theory of Computing , стр. 501–512, doi : 10.1145/73007.73055 , ISBN 0897913078, S2CID 1854173.
Ferreira, Afonso G.; Song, Siang W. (1992), «Достижение оптимальности для компоновки матрицы вентилей и сворачивания PLA: подход на основе теории графов», Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92) , Lecture Notes in Computer Science, т. 583, Springer-Verlag, стр. 139–153, doi : 10.1007/BFb0023825, hdl : 10068/43314 , ISBN 3-540-55284-7.
де Флюитер, Бабетта (1997), Алгоритмы для графов малой древовидной ширины (PDF) , докторская диссертация, Утрехтский университет , ISBN 90-393-1528-0, заархивировано из оригинала (PDF) 2011-07-24 , извлечено 2010-05-06.
Фомин, Федор В. (2003), «Путьевая ширина планарных и линейных графов», Графы и комбинаторика , 19 (1): 91–99, doi :10.1007/s00373-002-0490-z, S2CID 43123449.
Фомин, Федор В.; Хойе, Кьяртан (2006), «Путьевая ширина кубических графов и точные алгоритмы», Information Processing Letters , 97 (5): 191–196, doi :10.1016/j.ipl.2005.10.012.
Фомин Федор Владимирович; Крач, Дитер; Тодинка, Иоанн; Вилланджер, Ингве (2008), «Точные алгоритмы для ширины дерева и минимального заполнения», SIAM Journal on Computing , 38 (3): 1058–1079, doi : 10.1137/050643350, hdl : 1956/1151.
Фомин, Федор В.; Тиликос, Димитриос М. (2007), «О самодвойственности ширины пути в многогранных графовых вложениях», Журнал теории графов , 55 (1): 42–54, doi :10.1002/jgt.20219.
Гарбе, Ренате (1995), «Ширина дерева и ширина пути графов сравнимости интервальных порядков», Труды 20-го Международного семинара по теоретико-графовым концепциям в информатике (WG'94) , Lecture Notes in Computer Science, т. 903, Springer-Verlag, стр. 26–37, doi :10.1007/3-540-59071-4_35, ISBN 978-3-540-59071-2.
Головач, П.А. (1993), «Ширина разреза графа и число вершинных разделителей линейного графа», Дискретная математика и приложения , 3 (5): 517–522, doi :10.1515/dma.1993.3.5.517, S2CID 120745961.
Гуха, Судипто (2000), «Вложенные алгоритмы анализа и аппроксимации графов», Труды 41-го симпозиума IEEE по основам компьютерной науки (FOCS 2000) , стр. 126, doi :10.1109/SFCS.2000.892072, ISBN 0-7695-0850-2, S2CID 9854056.
Гурски, Франк; Ванке, Эгон (2007), «Линейные графы ограниченной ширины клики», Дискретная математика , 307 (22): 2734–2754, doi : 10.1016/j.disc.2007.01.020.
Густедт, Йенс (1993), «О ширине пути хордовых графов», Дискретная прикладная математика , 45 (3): 233–248, doi : 10.1016/0166-218X(93)90012-D.
Хабиб, Мишель; Мёринг, Рольф Х. (1994), «Древовидная ширина графов ко-сравнимости и новый параметр теории порядка», Order , 11 (1): 47–60, doi :10.1007/BF01462229, S2CID 2648030.
Глинени, Петр (2003), «Графы с критическим числом пересечений имеют ограниченную ширину пути», Журнал комбинаторной теории, Серия B , 88 (2): 347–367, doi : 10.1016/S0095-8956(03)00037-6.
Кашивабара, Т.; Фудзисава, Т. (1979), «NP-полнота задачи нахождения графа интервала с минимальным числом клик, содержащего заданный граф в качестве подграфа», Труды Международного симпозиума по схемам и системам , стр. 657–660.
Киннерсли, Нэнси Г. (1989), Изоляция множества препятствий для задач перестановки макетов (диссертация на докторскую степень), Университет штата Вашингтон, ProQuest 303738168; см. теорему 6.А, стр. 44.
Киннерсли, Нэнси Г. (1992), «Число разделительных вершин графа равно его ширине пути», Information Processing Letters , 42 (6): 345–350, doi : 10.1016/0020-0190(92)90234-M.
Киннерсли, Нэнси Г.; Лэнгстон, Майкл А. (1994), «Изоляция множества препятствий для задачи размещения матрицы вентилей», Дискретная прикладная математика , 54 (2–3): 169–213, doi : 10.1016/0166-218X(94)90021-3.
Кирусис, Лефтерис М.; Пападимитриу, Христос Х. (1985), «Интервальные графики и поиск», Дискретная математика , 55 (2): 181–184, doi : 10.1016/0012-365X(85)90046-9.
Kloks, Ton; Bodlaender, Hans L. (1992), "Аппроксимация ширины дерева и ширины пути некоторых классов совершенных графов", Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92) , Lecture Notes in Computer Science, т. 650, Springer-Verlag, стр. 116–125, doi :10.1007/3-540-56279-6_64, hdl : 1874/16672 , ISBN 978-3-540-56279-5.
Kloks, T.; Bodlaender, H .; Müller, H.; Kratsch, D. (1993), «Вычисление ширины дерева и минимального заполнения: все, что вам нужно, это минимальные разделители», Proc. 1st European Symposium on Algorithms (ESA'93) (Lecture Notes in Computer Science) , т. 726, Springer-Verlag, стр. 260–271, doi :10.1007/3-540-57273-2_61, ISBN 978-3-540-57273-2.
Клокс, Тон; Кратч, Дитер; Мюллер, Х. (1995), «Домино», Труды 20-го Международного семинара по теоретико-графовым концепциям в информатике (WG'94) , Lecture Notes in Computer Science, т. 903, Springer-Verlag, стр. 106–120, doi :10.1007/3-540-59071-4_41, ISBN 978-3-540-59071-2.
Кнейс, Иоахим; Молле, Даниэль; Рихтер, Стефан; Россманит, Питер (2005), «Алгоритмы, основанные на древовидной ширине разреженных графов», Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005) , Lecture Notes in Computer Science, т. 3787, Springer-Verlag, стр. 385–396, doi :10.1007/11604686_34, ISBN 978-3-540-31000-6.
Корах, Эфраим; Солель, Нир (1993), «Ширина дерева, ширина пути и ширина разреза», Дискретная прикладная математика , 43 (1): 97–101, doi : 10.1016/0166-218X(93)90171-J.
Корнаи, Андраш; Туза, Жолт (1992), «Узость, ширина пути и их применение в обработке естественного языка», Дискретная прикладная математика , 36 (1): 87–92, doi : 10.1016/0166-218X(92)90208-R.
Ленгауэр, Томас (1981), «Черно-белые камешки и разделение графов», Acta Informatica , 16 (4): 465–475, doi :10.1007/BF00264496, S2CID 19415148.
Лопес, Александр Д.; Лоу, Хунг-Фай С. (1980), "Метод плотной компоновки матрицы затворов для МОП СБИС", IEEE Transactions on Electron Devices , 27 (8): 1671–1675, Bibcode : 1980ITED...27.1671L, doi : 10.1109/T-ED.1980.20086, S2CID 64469353, Также в совместном выпуске, IEEE Journal of Solid-State Circuits 15 (4): 736–740, 1980.
Миллер, Джордж А. (1956), «Магическое число семь, плюс или минус два», Psychological Review , 63 (2): 81–97, doi : 10.1037/h0043158, hdl : 11858/00-001M-0000-002C-4646-B , PMID 13310704.
Мёринг, Рольф Х. (1990), «Проблемы с графами, связанные с компоновкой матрицы вентилей и складыванием PLA», в Тинхофер, Г.; Майр, Э.; Нольтемайер, Х.; и др. (ред.), Computational Graph Theory , Computing Supplementum, т. 7, Springer-Verlag, стр. 17–51, ISBN 3-211-82177-5.
Мониен, Б.; Садборо, И. Х. (1988), «Минимальный разрез является NP-полным для деревьев со взвешенными рёбрами», Теоретическая информатика , 58 (1–3): 209–229, doi : 10.1016/0304-3975(88)90028-X.
Оцуки, Тацуо; Мори, Хаджиму; Кух, Эрнест С.; Кашивабара, Тошинобу; Фудзисава, Тошио (1979), «Одномерное назначение логических вентилей и интервальные графы», IEEE Transactions on Circuits and Systems , 26 (9): 675–684, doi :10.1109/TCS.1979.1084695.
Peng, Sheng-Lung; Ho, Chin-Wen; Hsu, Tsan-sheng; Ko, Ming-Tat; Tang, Chuan Yi (1998), "Линейный алгоритм построения оптимальной стратегии поиска узлов дерева", в Hsu, Wen-Lian; Kao, Ming-Yang (ред.), Computing and Combinatorics, 4-я ежегодная международная конференция, COCOON '98, Тайбэй, Тайвань, RoC, 12–14 августа 1998 г., Труды , Lecture Notes in Computer Science, т. 1449, Springer, стр. 279–288, doi :10.1007/3-540-68535-9_32, ISBN 978-3-540-64824-6
Проскуровски, Анджей; Телле, Ян Арне (1999), «Классы графов с моделями ограниченного интервала» (PDF) , Дискретная математика и теоретическая информатика , 3 : 167–176.
Робертсон, Нил ; Сеймур, Пол (1983), «Миноры графа. I. Исключение леса», Журнал комбинаторной теории, Серия B , 35 (1): 39–61, doi : 10.1016/0095-8956(83)90079-5.
Робертсон, Нил ; Сеймур, Пол (2003), «Миноры графа. XVI. Исключение непланарного графа», Журнал комбинаторной теории, Серия B , 89 (1): 43–76, doi : 10.1016/S0095-8956(03)00042-X.
Робертсон, Нил ; Сеймур, Пол Д. (2004), «Миноры графа. XX. Гипотеза Вагнера», Журнал комбинаторной теории, Серия B , 92 (2): 325–357, doi : 10.1016/j.jctb.2004.08.001.
Шеффлер, Петра (1990), «Линейный алгоритм для ширины пути деревьев», в Бодендиек, Р.; Хенн, Р. (ред.), Темы комбинаторики и теории графов , Physica-Verlag, стр. 613–620.
Шеффлер, Петра (1992), «Оптимальное вложение дерева в интервальный граф за линейное время», в Нешетржил, Ярослав ; Фидлер, Мирослав (ред.), Четвертый чехословацкий симпозиум по комбинаторике, графам и сложности , Elsevier.
Скодинис, Константин (2000), «Вычисление оптимальных линейных схем деревьев за линейное время», Труды 8-го Европейского симпозиума по алгоритмам (ESA 2000) , Lecture Notes in Computer Science, т. 1879, Springer-Verlag, стр. 403–414, doi :10.1007/3-540-45253-2_37, ISBN 978-3-540-41004-1.
Скодинис, Константин (2003), «Построение линейных древовидных структур, оптимальных с точки зрения разделения вершин за линейное время», Журнал алгоритмов , 47 (1): 40–59, doi :10.1016/S0196-6774(02)00225-0.
Suchan, Karol; Todinca, Ioan (2007), "Путьевая ширина графов с дугами окружности", Proc. 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007) , Lecture Notes in Computer Science, т. 4769, Springer-Verlag, стр. 258–269, doi :10.1007/978-3-540-74839-7_25, ISBN 978-3-540-74838-0.
Suderman, Matthew (2004), «Ширина пути и многослойные рисунки деревьев» (PDF) , International Journal of Computational Geometry and Applications , 14 (3): 203–225, doi :10.1142/S0218195904001433, архивировано из оригинала (PDF) 2003-05-03.
Такахаси, Ацуси; Уэно, Шуичи; Кадзитани, Ёдзи (1994), «Минимальные ациклические запрещённые миноры для семейства графов с ограниченной шириной пути», Дискретная математика , 127 (1–3): 293–304, doi : 10.1016/0012-365X(94)90092-2.