Путевая ширина

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

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

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

Определение
Пример графа G с путевой шириной 2 и его путевая декомпозиция ширины 2. В нижней части рисунка приведён тот же граф и путевая декомпозиция с добавленными цветами для выразительности. (Этот пример взят из книги Бодлаендера[13], и добавлены цвета)

В первой знаменитой серии статей о минорах минорах графа Робертсон и Сеймур[2] определили путевую декомпозицию графа G как последовательность подмножеств Xi вершин графа G с двумя свойствами:

  1. Для каждого ребра G, существует i, такого, что обе конечные точки ребра принадлежат подмножеству Xi
  2. Для любых трёх индексов i ≤ j ≤ k, Xi ∩ Xk ⊆ Xj.

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

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

Альтернативные описания

Как пишет Бодлаендер[3], путевая ширина может быть описана многими эквивалентными способами.

Склеивание последовательностей

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

Интервальная толщина
Интервальный граф с путевой шириной два, на единицу меньшей числа четырёх максимальных клик ABC, ACD, CDE и CDF.

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

В одном направлении, предположим, что древесная декомпозиция графа G задана. Тогда можно представить вершины декомпозиции как точки на прямой (в том порядке, в котором они входят в путь) и представить каждую вершину v как замкнутый интервал, имеющий эти точки в качестве конечных точек. Например, пусть (X1, . . . , Xr) — путевая декомпозиция графа G, точки на прямой — [1, . . . , r], тогда представление вершины 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. Величину вершинного разделения ввели Эллис, Садбороу и Тёрнер[15] и она равна путевой ширине графа G[16][17]. Это следует из ранее упомянутой эквивалентности интервальных графов и кликовых чисел — если G является подграфом интервального графа I, представленного (как на рисунке) таким образом, что все концы интервалов различны, то порядок левых концов интервалов графа I имеют величину вершинного разделения на единицу меньше кликового числа графа I. В другом направлении, из линейного упорядочения графа G можно получить интервальное представление, в котором левая конечная точка интервала для вершины v является позицией в упорядочении, а правая конечная точка является позицией соседа v, который в упорядочении последний.

Вершинно-поисковое число

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

Границы
Граф-гусеница, максимальный граф с путевой шириной один.

Любой граф с 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-пути. В частности, максимальные графы путевой ширины единица — это в точности графы-гусеницы [19].

Поскольку путевые декомпозиции являются специальными случаями древесных декомпозиций, путевая ширина любого графа больше либо равна его древесной ширине. Путевая ширина также меньше или равна ширине разреза, минимального числа рёбер, пересекающих любое сечение между вершинами с меньшим индексом и большим индексом в оптимальном линейном упорядочении вершин графа. Это следует из факта, что величина вершинного разделения, число вершин с меньшим индексом с соседами, имеющими больший индекс, не больше числа разрезающих рёбер[20][21]. По такой же причине ширина разреза не превосходит путевой ширины, умноженной на максимальную степень вершин в данном графе[22][23].

Любой лес с n вершинами имеет путевую ширину O(log n)[24][25][26]. Для леса можно всегда найти постоянное число вершин, удаление которых приводит к лесу, который можно разбить на два меньших леса с максимум 2n/3 вершин в каждом из этих лесов. Линейное упорядочение, образованное рекурсивным применением такого разбиения, имеет логарифмическое поисковое число для вершин. Та же техника, применённая к древесной декомпозиции графа, показывает, что если древесная ширина графа G с n вершинами равна t, то путевая ширина графа G равна O(t log n)[27][28]. Поскольку внешнепланарные графы, параллельно-последовательные графы и графы Халина все имеют ограниченную древесную ширину, все они имеют максимум логарифмическую путевую ширину.

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

В любом планарном графе путевая ширина в худшем случае пропорциональна квадратному корню от числа вершин[31]. Один из способов поиска путевой декомпозиции с такой шириной — (подобно путевой декомпозиции с логарифмической шириной лесов, описанной выше) использовать теорему о планарном разбиении, чтобы найти множество из O(√n) вершин, удаление которых разбивает граф на два подграфа с максимум 2n/3 вершинами в каждом, и соединить рекурсивно построенные для этих двух подграфов путевые декомпозиции. Та же техника применима к любому классу графов, для которых выполняется подобная теорема о разбиении[32]. Поскольку любое семейство графов, замкнутое относительно взятия миноров, как и в случае планарных графов, имеет разбивающее множество вершин размера O(√n)[33], отсюда следует, что путевая ширина графов в любом фиксированном замкнутом относительно миноров семействе снова равна O(√n). Для некоторых классов планарных графов путевая ширина графа и путевая ширина его двойственного графа должны лежать в интервале, границы которого линейно зависят от значений — такие границы известны для двусвязных внешнепланарных графов[34][35] и для графов многогранников[36][37]. Для двусвязных планарных графов путевая ширина двойственного графа меньше, чем путевая ширина рёберного графа[38]. Остаётся открытым вопрос, являются ли путевые ширины планарного графа и его двойственного всегда в линейных границах для остальных случаев.

Для некоторых классов графов доказано, что путевая ширина и древесная ширина всегда равны друг другу — это верно для кографов[39], графов перестановки [40], дополнений графов сравнимости[41] и графов сравнимости интервальных порядков[42].

Нерешённые проблемы математики: Какова максимальная путевая ширина кубического графа с вершинами?

В любом кубическом графе, или, более обще, любом графе с максимальной степенью вершин 3, путевая ширина не превосходит n/6 + o(n), где n — число вершин графа. Существуют кубические графы с путевой шириной 0.082n, но неизвестно, как сократить этот разрыв между нижней границей и верхней границей n/6[43].

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

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

Фиксированно-параметрически разрешимость

Путевая ширина фиксированно-параметрически разрешима — для любой постоянной k можно проверить, не превосходит ли путевая ширина величину k, и если не превосходит, найти путевую декомпозицию ширины k за линейное время [8]. В целом, эти алгоритмы работают в два этапа. На первом этапе используется предположение, что граф имеет путевую ширину k, для поиска путевой декомпозиции или древесной декомпозиции. Эта декомпозиция не оптимальна, но её ширина может быть ограничена функцией от k. На втором этапе применяется алгоритм динамического программирования для поиска оптимальной декомпозиции. Однако временные границы для известных алгоритмов этого типа экспоненциальны от k2 и не представляют практического интереса, разве что для малых значений k[45]. Для случая k = 2 Фляйтер дал алгоритм с линейным временем работы, основанный на структурной декомпозиции графов с путевой шириной 2 [46].

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

Бодлаендер [9] дал обозрение сложности задач вычисления путевой ширины на различных специальных классах графов. Определение, превосходит ли путевая ширина графа G величину k, остаётся NP-полной задачей, если G берётся из графов ограниченной степени[47], планарные графы[47], планарных графов ограниченной степени[47], хордальных графов[48], хордальных домино[49], дополнений графов сравнимости[41], и двудольных дистанционно-наследуемых графов[50]. Отсюда немедленно следует, что задача также NP-полна для семейств графов, содержащих двудольные дистанционно-наследуемые графы, включая двудольные графы, хордальные двудольные графы дистанционно-наследуемые графы и круговые графы[50].

Однако путевую ширину можно вычислить за линейное время для деревьев и лесов [10]. Можно вычислить эту величину за полиномиальное время для графов ограниченной древесной ширины, в которые входят параллельно-последовательные графы, внешнепланарные графы и графы Халина [8], а также расщепляемые графы[51][48], дополнения хордальных графов [52], графы перестановки[40], кографы[39], графы дуг окружности[53], графы сравнимости интервальных порядков[42], и, конечно, сами интервальные графы, поскольку для них путевая ширина просто на единицу меньше максимального числа интервального накрытия любой точки в интервальном представлении графа.

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

NP-трудной задачей является аппроксимация путевой ширины графа аддитивной константой[7]. Лучший известный аппроксимационный коэффициент аппроксимационных алгоритмов полиномиального времени для путевой ширины равен O((log n)3/2)[54]. Ранние аппроксимационные алгоритмы для путевой ширины можно найти у Бодлаендера, Гилберта, Хафштейнссона, Клокса[7] и Гуха[55]. Для аппроксимации ограниченных классов графов см. книгу Клокса и Бодлаендера[51].

Миноры графа

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

Исключение леса

Если семейство F графов замкнуто по отношению к операции взятия миноров (любой минор члена семейства F также содержится в F), тогда по теореме Робертсона – Сеймура семейство F можно охарактеризовать как графы, не содержащие миноров из X, где X — конечное множество запрещённых миноров [56]. Например, теорема Вагнера утверждает, что планарные графы — это графы, которые не содержат ни полного графа K5, ни полного двудольного графа K3,3 в качестве миноров. Во многих случаях свойства F и свойства X тесно связаны, и первый результат такого типа получили Робертсон и Сеймур [2] и он связывает существование ограниченной путевой ширины с наличием леса в семействе запрещённых миноров. Конкретнее, определим семейство F графов как имеющее ограниченную путевую ширину, если существует константа p, такая, что любой граф из F имеет путевую ширину, не превосходящую p. Тогда минорно-замкнутое семейство F имеет ограниченную путевую ширину тогда и только тогда, когда множество X запрещённых миноров для F включает хотя бы один лес.

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

Оценки путевой ширины
Запрещённые миноры для графов с путевой шириной 1.

Свойство иметь путевую ширину не больше p является, само по себе, замкнутым по взятию миноров свойством — если G имеет путевую декомпозицию с шириной, не превосходящей p, то та же самая путевая декомпозиция остаётся верной, если удалить любое ребро из G, а также любая вершина может быть удалена из графа G и его путевой декомпозиции без увеличения ширины. Стягивание ребра также может быть завершено без увеличения ширины декомпозиции путём слияния подпутей, представляющих два конца стягиваемого ребра. Таким образом, графы с путевой шириной, не превосходящей p, могут быть охарактеризованы множеством Xp запрещённых миноров[56][16][60][61].

Хотя Xp обязательно включает по меньшей мере один лес, неверно, что все графы в Xp являются лесами. Например, X1 состоит из двух графов, дерева с семью вершинами и треугольника K3. Однако множество деревьев в Xp можно точно описать — это в точности те деревья, которые можно образовать из трёх деревьев из Xp − 1 путём образования нового корня и соединения его рёбрами с произвольно выбранными вершинами меньших деревьев. Например, дерево с семью вершинами в X1 образовано из деревьев с двумя вершинами (одно ребро) из X0. Основываясь на этом построении, можно показать, что число запрещённых миноров в Xp не меньше (p!)2[16][60][61]. Полное множество X2 запрещённых миноров для графов с путевой шириной 2 вычислено. Это множество содержит 110 различных графов[62].

Структурная теория

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

Приложения

СБИС

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

Отцуки, Мори, Кух и Кашивабара[64] использовали интервальную толщину для моделирования числа проводников, необходимых в одномерном расположении цепей СБИС, образованных множеством модулей, которые необходимо соединить системой сетей. В их модели можно образовать граф, в котором вершины представляют цепи и в которой две вершины соединены ребром, если их цепи соединены к одному и тому же модулю. То есть если модули и цепи понимаются как вершины и гиперрёбра гиперграфа, то граф, образованный из них, является рёберным графом гиперграфа. Интервальное представление суперграфа этого рёберного графа вместе с раскраской суперграфа описывает расположение цепей вдоль горизонтальных дорожек (одна дорожка на каждый цвет), так что модули могут быть расположены вдоль дорожек в линейном порядке и соединены с нужными цепями. Из факта, что интервальные графы являются совершенными[65], следует, что число цветов, необходимых для оптимальной раскладки такого типа, равно кликовому числу интервального дoполнения графа цепей.

Матричная укладка переключателей[66] является специфическим видом КМОП СБИС укладки для цепей алгебры логики. В матричных укладках переключателей сигнал распространяется вдоль "линий" (вертикальных отрезков), в то время как каждый переключатель образуется последовательностью элементов, располагающихся на горизонтальном отрезке. Таким образом, горизонтальные отрезки для каждого переключателя должны пересекать вертикальные отрезки для каждой линии, которая служит входом или выходом переключателя. Как и в укладках Отцуки, Мори, Куха и Кашивабара[64] укладка такого типа, минимизирующая число вертикальных прямых, может быть вычислена путём вычисления путевой ширины графа, имеющего прямые в качестве вершин, а пары прямых, принадлежащих переключателю, в качестве рёбер[67]. Тот же алгоритмический подход может быть также использован для моделирования задач укладки в программируемых логических интегральных схемах[68][69].

Визуализация графов

Путевая ширина имеет несколько приложений для визуализации графов:

  • Минимальные графы, имеющие заданное число пересечений, имеют путевую ширину, ограниченную функцией от числа пересечений[70].
  • Число параллельных прямых, на которых можно расположить вершины дерева без пересечения рёбер (при различных естественных ограничениях на способы, которыми смежные вершины могут быть помещены на прямых с учётом последовательности прямых) пропорционально путевой ширине дерева[71].
  • k-пересечённый h-уровневый рисунок графа G — это расположение вершин графа G на h различных горизонтальных прямых с рёбрами в виде монотонных (представленных ломаными) путей между прямыми, в котором имеется не более k пересечений. Графы с таким представлением имеют путевую ширину, ограниченную функцией от h и k. Таким образом, если величины h и k постоянны, можно за линейное время определить, имеется ли у графа k-пересечённый h-уровневый рисунок[72].
  • Граф с n вершинами и путевой шириной p может быть вложен в трёхмерную решётку размера p × p × n таким образом, что никакие два ребра (представленные прямолинейными отрезками между точками решётки) не пересекают друг друга. Таким образом, графы ограниченной путевой ширины имеют вложения этого типа с линейным объёмом[73].

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

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

Для любого фиксированного числа w регистров в машине можно определить за линейное время, может ли фрагмент линейного кода быть переупорядочен так, что для кода потребуется максимум w регистров. Если величина вершинного разделения топологического упорядочения не превосходит w, минимальное вершинное разделение среди всех упорядочений не может быть больше, так что неориентированные графы, образованные игнорированием ориентации НАГ, описанного выше, должны иметь путевую ширину, не превосходящую w. Можно проверить, верно ли это с помощью известных фиксированно-параметрически разрешимых алгоритмов для путевой ширины, и если верно, найти путевую декомпозицию для неориентированных графов за линейное время в предположении, что w является константой. Как только древесная декомпозиция найдена, топологическое упорядочение с шириной w (если такое существует) может быть найдено с использованием динамического программирования, опять же за линейное время[74].

Лингвистика

Карнаи и Туца[75] описали приложение путевой ширины для обработки естественного языка. В этом приложении предложения моделируются в виде графов, в которых вершины представляют слова, а рёбра представляют связи между словами. Например, если прилагательное модифицирует существительное, то граф имеет ребро между этими двумя словами. Ввиду ограниченного объёма кратковременной человеческой памяти Миллер[76], Корнаи и Туца утверждают, что этот граф должен иметь ограниченную путевую ширину (конкретнее, они утверждают, что эта путевая ширина не превосходит шести), в противном случае люди не могли бы распознавать речь правильно.

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

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

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

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

Примечания
  1. Diestel, Kühn, 2005.
  2. Robertson, Seymour, 1983.
  3. Bodlaender, 1998.
  4. Множество используемых в статье терминов можно найти во введении в диссертацию Ф. В. Фомина ((Фомин 1996))
  5. Robertson, Seymour, 2003.
  6. Kashiwabara, Fujisawa, 1979; Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979; Lengauer, 1981; Arnborg, Corneil, Proskurowski, 1987.
  7. Bodlaender, Gilbert, Hafsteinsson, Kloks, 1992.
  8. Bodlaender (1996); Bodlaender, Kloks (1996)
  9. Bodlaender, 1994.
  10. Möhring, 1990; Scheffler, 1990; Ellis, Sudborough, Turner, 1994; Coudert, Huc, Mazauric, 1998; Peng, Ho, Hsu, Ko, Tang, 1998; Skodinis, 2000; Skodinis (2003).
  11. Arnborg, 1985.
  12. Aspvall, Proskurowski, Telle, 2000.
  13. Bodlaender, 1994, с. 1–2.
  14. Bodlaender, 1998, с. 13, Theorem 29.
  15. Ellis, Sudborough, Turner, 1983.
  16. Kinnersley, 1992.
  17. Bodlaender, 1998, с. Theorem 51.
  18. Kirousis, Papadimitriou, 1985.
  19. Proskurowski, Telle, 1999.
  20. Korach, Solel, 1993, с. 99, Lemma 3.
  21. Bodlaender, 1998, с. 24, Theorem 47.
  22. Korach, Solel, 1993, с. 99, Lemma 1.
  23. Bodlaender, 1998, с. 24, Theorem 49.
  24. Korach, Solel, 1993, с. 99, Theorem 5.
  25. Bodlaender, 1998, с. 30, Theorem 66.
  26. Шеффлер (Scheffler (1992)) даёт более сильную границу log3(2n + 1) путевой ширины леса с n вершинами.
  27. Korach, Solel, 1993, с. 100, Theorem 6.
  28. Bodlaender, 1998, с. 10, Corollary 24.
  29. Gurski, Wanke, 2007.
  30. Golovach, 1993.
  31. Bodlaender, 1998, с. 10, Corollary 23.
  32. Bodlaender, 1998, с. 9, Theorem 20.
  33. Alon, Seymour, Thomas, 1990.
  34. Bodlaender, Fomin, 2002.
  35. Coudert, Huc, Sereni, 2007.
  36. Fomin, Thilikos, 2007.
  37. Amini, Huc, Pérennes, 2009.
  38. Fomin, 2003.
  39. Bodlaender, Möhring, 1990.
  40. Bodlaender, Kloks, Kratsch, 1993.
  41. Habib, Möhring, 1994.
  42. Garbe, 1995.
  43. Fomin, Høie, 2006.
  44. Fomin, Kratsch, Todinca, Villanger, 2008.
  45. Downey, Fellows, 1999, с. 12.
  46. de Fluiter, 1997.
  47. Monien, Sudborough, 1988.
  48. Gusted, 1993.
  49. Kloks, Kratsch, Müller, 1995. Хордальное домино — это хордальный граф, в котором любая вершина принадлежит максимум двум максимальным кликам
  50. Kloks, Bodlaender, Müller, Kratsch, 1993.
  51. Kloks, Bodlaender, 1992.
  52. Гарбе (Garbe (1995)) приписывает этот результат тезисам диссертации Тона Клокса 1993 года. Алгоритм полиномиального времени Гарбе для графов сравнимости интервальных упорядочений обобщает этот результат, поскольку любой хордальный граф должен быть графом сравнимости такого типа.
  53. Suchan, Todinca, 2007.
  54. Feige, Hajiaghayi, Lee, 2005.
  55. Guha, 2000.
  56. Robertson, Seymour, 2004.
  57. Bienstock, Robertson, Seymour, Thomas, 1991.
  58. Diestel, 1995.
  59. Cattell, Dinneen, Fellows, 1996.
  60. Takahashi, Ueno, Kajitani, 1994.
  61. Bodlaender, 1998, с. 8.
  62. Kinnersley, Langston, 1994.
  63. Demaine, Hajiaghayi, Kawarabayashi, 2005.
  64. Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979.
  65. Berge, 1967.
  66. Lopez, Law, 1980.
  67. Fellows, Langston, 1989.
  68. Möhring, 1990.
  69. Ferreira, Song, 1992.
  70. Hliněny, 2003.
  71. Suderman, 2004.
  72. Dujmović, Fellows, Kitching и др., 2008.
  73. Dujmović, Morin, Wood, 2003.
  74. Bodlaender, Gustedt, Telle, 1998.
  75. Kornai, Tuza, 1992.
  76. Miller, 1956.
  77. Kneis, Mölle, Richter, Rossmanith, 2005.
  78. Björklund, Husfeldt, 2008.

Литература
  • Noga Alon, Paul Seymour, Robin Thomas. Proc. 22nd ACM Symp. on Theory of Computing (STOC 1990). — 1990. — С. 293—299. — ISBN 0897913612. — doi:10.1145/100216.100254..
  • Omid Amini, Florian Huc, Stéphane Pérennes. On the path-width of planar graphs // SIAM Journal on Discrete Mathematics. — 2009. — Т. 23, вып. 3. — С. 1311—1316. — doi:10.1137/060670146..
  • Stefan Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey // BIT. — 1985. — Т. 25, вып. 1. — С. 2—23. — doi:10.1007/BF01934985..
  • Stefan Arnborg, Derek G. Corneil, Andrzej Proskurowski. Complexity of finding embeddings in a $k$-tree // SIAM Journal on Algebraic and Discrete Methods. — 1987. — Т. 8, вып. 2. — С. 277—284. — doi:10.1137/0608024..
  • Bengt Aspvall, Andrzej Proskurowski, Jan Arne Telle. Memory requirements for table computations in partial k-tree algorithms // Algorithmica. — 2000. — Т. 27, вып. 3. — С. 382—394. — doi:10.1007/s004530010025..
  • Claude Berge. Graph Theory and Theoretical Physics. — New York: Academic Press, 1967. — С. 155—165..
  • Dan Bienstock, Neil Robertson, Paul Seymour, Robin Thomas. Quickly excluding a forest // Journal of Combinatorial Theory, Series B. — 1991. — Т. 52, вып. 2. — С. 274—283. — doi:10.1016/0095-8956(91)90068-U..
  • Andreas Björklund, Thore Husfeldt. Exact algorithms for exact satisfiability and number of perfect matchings // Algorithmica. — 2008. — Т. 52, вып. 2. — С. 226—249. — doi:10.1007/s00453-007-9149-8..
  • Hans L. Bodlaender. A tourist guide through treewidth // Acta Cybernetica. — 1994. — Т. 11.
  • Hans L. Bodlaender. Developments in Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 November 1992) / Jürgen Dassow, Alisa Kelemenová. — Gordon and Breach, 1994. — Т. 6. — С. 1—20. — (Topics in Computer Mathematics)..
  • Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth // SIAM Journal on Computing. — 1996. — Т. 25, вып. 6. — С. 1305—1317. — doi:10.1137/S0097539793251219..
  • Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth (англ.) // Theoretical Computer Science. — 1998. — Vol. 209, iss. 1—2. — P. 1—45. — doi:10.1016/S0304-3975(97)00228-4..
  • Hans L. Bodlaender, Fedor V. Fomin. Approximation of pathwidth of outerplanar graphs // Journal of Algorithms. — 2002. — Т. 43, вып. 2. — С. 190—200. — doi:10.1016/S0196-6774(02)00001-9..
  • Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, Ton Kloks. Graph-Theoretic Concepts in Computer Science. — 1992. — Т. 570. — С. 1—12. — (Lecture Notes in Computer Science). — ISBN 978-3-540-55121-8. — doi:10.1007/3-540-55121-2_1..
  • Hans L. Bodlaender, Jens Gustedt, Jan Arne Telle. Proc. 9th ACM–SIAM Symposium on Discrete Algorithms (SODA '98). — 1998. — С. 574—583..
  • Hans L. Bodlaender, Ton Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs // Journal of Algorithms. — 1996. — Т. 21, вып. 2. — С. 358—402. — doi:10.1006/jagm.1996.0049..
  • Hans L. Bodlaender, Ton Kloks, Dieter Kratsch. Proc. 20th International Colloquium on Automata, Languages and Programming (ICALP 1993). — Springer-Verlag, 1993. — Т. 700. — С. 114—125. — (Lecture Notes in Computer Science). — ISBN 978-3-540-56939-8. — doi:10.1007/3-540-56939-1_66..
  • Hans L. Bodlaender, Rolf H. Möhring. Proc. 2nd Scandinavian Workshop on Algorithm Theory. — Springer-Verlag, 1990. — Т. 447. — С. 301—309. — (Lecture Notes in Computer Science). — ISBN 978-3-540-52846-3. — doi:10.1007/3-540-52846-6_99..
  • Kevin Cattell, Michael J. Dinneen, Michael R. Fellows. A simple linear-time algorithm for finding path-decompositions of small width // Information Processing Letters. — 1996. — Т. 57, вып. 4. — С. 197—203. — doi:10.1016/0020-0190(95)00190-5..
  • David Coudert, Florian Huc, Dorian Mazauric. Proc. 22nd Int. Symp. Distributed Computing. — Springer-Verlag, 1998. — Т. 5218. — С. 500—501. — (Lecture Notes in Computer Science). — ISBN 978-3-540-87778-3. — doi:10.1007/978-3-540-87779-0_36..
  • David Coudert, Florian Huc, Jean-Sébastien Sereni. Pathwidth of outerplanar graphs // Journal of Graph Theory. — 2007. — Т. 55, вып. 1. — С. 27—41. — doi:10.1002/jgt.20218..
  • Reinhard Diestel. Graph Minors I: a short proof of the path-width theorem // Combinatorics, Probability and Computing. — 1995. — Т. 4, вып. 1. — С. 27—30. — doi:10.1017/S0963548300001450..
  • Reinhard Diestel, Daniela Kühn. Graph minor hierarchies // Discrete Applied Mathematics. — 2005. — Т. 145, вып. 2. — С. 167—182. — doi:10.1016/j.dam.2004.01.010..
  • Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi. Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005). — 2005. — С. 637—646. — ISBN 0-7695-2468-0. — doi:10.1109/SFCS.2005.14..
  • Rod G. Downey, Michael R. Fellows. Parameterized Complexity. — Springer-Verlag, 1999. — ISBN 0-387-94883-X..
  • V. Dujmović, M.R. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, S. Whitesides, David R. Wood. On the parameterized complexity of layered graph drawing // Algorithmica. — 2008. — Т. 52, вып. 2. — С. 267—292. — doi:10.1007/s00453-007-9151-1..
  • Vida Dujmović, Pat Morin, David R. Wood. Proc. 10th International Symposium on Graph Drawing (GD 2002). — Springer-Verlag, 2003. — Т. 2528. — С. 42—53. — (Lecture Notes in Computer Science)..
  • J. A. Ellis, I. H. Sudborough, J. S. Turner. Proc. 1983 Allerton Conf. on Communication, Control, and Computing. — 1983.. As cited by Monien & Sudborough (1988).
  • J. A. Ellis, I. H. Sudborough, J. S. Turner. The vertex separation and search number of a tree // Information and Computation. — 1994. — Т. 113, вып. 1. — С. 50—79. — doi:10.1006/inco.1994.1064..
  • Uriel Feige, Mohammadtaghi Hajiaghayi, James R. Lee. Proc. 37th ACM Symposium on Theory of Computing (STOC 2005). — 2005. — С. 563—572. — ISBN 1581139608. — doi:10.1145/1060590.1060674..
  • Michael R. Fellows, Michael A. Langston. Proc. 21st ACM Symposium on Theory of Computing. — 1989. — С. 501—512. — ISBN 0897913078. — doi:10.1145/73007.73055..
  • Afonso G. Ferreira, Siang W. Song. Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92). — Springer-Verlag, 1992. — Т. 583. — С. 139—153. — (Lecture Notes in Computer Science). — ISBN 3-540-55284-7. — doi:10.1007/BFb0023825..
  • Babette de Fluiter. Algorithms for Graphs of Small Treewidth. — Utrecht University, 1997. — (Ph.D. thesis). — ISBN 90-393-1528-0..
  • Fedor V. Fomin. Pathwidth of planar and line graphs // Graphs and Combinatorics. — 2003. — Т. 19, вып. 1. — С. 91—99. — doi:10.1007/s00373-002-0490-z..
  • Fedor V. Fomin, Kjartan Høie. Pathwidth of cubic graphs and exact algorithms // Information Processing Letters. — 2006. — Т. 97, вып. 5. — С. 191—196. — doi:10.1016/j.ipl.2005.10.012..
  • Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, Yngve Villanger. Exact algorithms for treewidth and minimum fill-in // SIAM Journal on Computing. — 2008. — Т. 38, вып. 3. — С. 1058—1079. — doi:10.1137/050643350..
  • Fedor V. Fomin, Dimitrios M. Thilikos. On self duality of pathwidth in polyhedral graph embeddings // Journal of Graph Theory. — 2007. — Т. 55, вып. 1. — С. 42—54. — doi:10.1002/jgt.20219..
  • Renate Garbe. Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94). — Springer-Verlag, 1995. — Т. 903. — С. 26—37. — (Lecture Notes in Computer Science). — ISBN 978-3-540-59071-2. — doi:10.1007/3-540-59071-4_35..
  • P. A. Golovach. The cutwidth of a graph and the vertex separation number of the line graph // Discrete Mathematics and Applications. — 1993. — Т. 3, вып. 5. — С. 517—522. — doi:10.1515/dma.1993.3.5.517..
  • Sudipto Guha. Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS 2000). — 2000. — С. 126. — ISBN 0-7695-0850-2. — doi:10.1109/SFCS.2000.892072..
  • Frank Gurski, Egon Wanke. Line graphs of bounded clique-width // Discrete Mathematics. — 2007. — Т. 307, вып. 22. — С. 2734—2754. — doi:10.1016/j.disc.2007.01.020..
  • Jens Gusted. On the pathwidth of chordal graphs // Discrete Applied Mathematics. — 1993. — Т. 45, вып. 3. — С. 233—248. — doi:10.1016/0166-218X(93)90012-D..
  • Michel Habib, Rolf H. Möhring. Treewidth of cocomparability graphs and a new order-theoretic parameter // Order. — 1994. — Т. 11, вып. 1. — С. 47—60. — doi:10.1007/BF01462229..
  • Petr Hliněny. Crossing-number critical graphs have bounded path-width // Journal of Combinatorial Theory, Series B. — 2003. — Т. 88, вып. 2. — С. 347—367. — doi:10.1016/S0095-8956(03)00037-6..
  • T. Kashiwabara, T. Fujisawa. Proc. International Symposium on Circuits and Systems. — 1979. — С. 657—660..
  • Nancy G. Kinnersley. The vertex separation number of a graph equals its path-width // Information Processing Letters. — 1992. — Т. 42, вып. 6. — С. 345—350. — doi:10.1016/0020-0190(92)90234-M..
  • Nancy G. Kinnersley, Michael A. Langston. Obstruction set isolation for the gate matrix layout problem // Discrete Applied Mathematics. — 1994. — Т. 54, вып. 2—3. — С. 169—213. — doi:10.1016/0166-218X(94)90021-3..
  • Lefteris M. Kirousis, Christos H. Papadimitriou. Interval graphs and searching // Discrete Mathematics. — 1985. — Т. 55, вып. 2. — С. 181—184. — doi:10.1016/0012-365X(85)90046-9. (недоступная ссылка).
  • Ton Kloks, Hans L. Bodlaender. Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92). — Springer-Verlag, 1992. — Т. 650. — С. 116—125. — (Lecture Notes in Computer Science). — ISBN 978-3-540-56279-5. — doi:10.1007/3-540-56279-6_64..
  • T. Kloks, H. Bodlaender, H. Müller, D. Kratsch. Proc. 1st European Symposium on Algorithms (ESA'93). — Springer-Verlag, 1993. — Т. 726. — С. 260—271. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-57273-2_61..
  • Ton Kloks, Dieter Kratsch, H. Müller. Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94). — Springer-Verlag, 1995. — Т. 903. — С. 106—120. — (Lecture Notes in Computer Science). — ISBN 978-3-540-59071-2. — doi:10.1007/3-540-59071-4_41..
  • Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith. Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005). — Springer-Verlag, 2005. — Т. 3787. — С. 385—396. — (Lecture Notes in Computer Science). — ISBN 978-3-540-31000-6. — doi:10.1007/11604686_34..
  • Ephraim Korach, Nir Solel. Tree-width, path-width, and cutwidth // Discrete Applied Mathematics. — 1993. — Т. 43, вып. 1. — С. 97—101. — doi:10.1016/0166-218X(93)90171-J..
  • András Kornai, Zsolt Tuza. Narrowness, path-width, and their application in natural language processing // Discrete Applied Mathematics. — 1992. — Т. 36, вып. 1. — С. 87—92. — doi:10.1016/0166-218X(92)90208-R..
  • Thomas Lengauer. Black-white pebbles and graph separation // Acta Informatica. — 1981. — Т. 16, вып. 4. — С. 465—475. — doi:10.1007/BF00264496..
  • Alexander D. Lopez, Hung-Fai S. Law. A dense gate matrix layout method for MOS VLSI // IEEE Transactions on Electron Devices. — 1980. — Т. ED—27, вып. 8. — С. 1671—1675. — doi:10.1109/T-ED.1980.20086..
  • George A. Miller. The Magical Number Seven, Plus or Minus Two // Psychological Review. — 1956. — Т. 63, вып. 2. — С. 81—97. — doi:10.1037/h0043158. — PMID 13310704..
  • Rolf H. Möhring. Computational Graph Theory / G. Tinhofer, E. Mayr, H. Noltemeier, M. Sysło. — Springer-Verlag, 1990. — Т. 7. — С. 17—51. — (Computing Supplementum). — ISBN 3-211-82177-5..
  • B. Monien, I. H. Sudborough. Min cut is NP-complete for edge weighted trees (англ.) // Theoretical Computer Science. — 1988. — Vol. 58, iss. 1—3. — P. 209—229. — doi:10.1016/0304-3975(88)90028-X..
  • Tatsuo Ohtsuki, Hajimu Mori, Ernest S. Kuh, Toshinobu Kashiwabara, Toshio Fujisawa. One-dimensional logic gate assignment and interval graphs // IEEE Transactions on Circuits and Systems. — 1979. — Т. 26, вып. 9. — С. 675—684. — doi:10.1109/TCS.1979.1084695..
  • Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, Chuan Yi Tang. Proc. 4th Int. Conf. Computing and Combinatorics (COCOON'98). — Springer-Verlag, 1998. — Т. 1449. — С. 197—205. — (Lecture Notes in Computer Science)..
  • Andrzej Proskurowski, Jan Arne Telle. Classes of graphs with restricted interval models (англ.) // Theoretical Computer Science. — 1999. — Vol. 3. — P. 167—176..
  • Neil Robertson, Paul Seymour. Graph minors. I. Excluding a forest // Journal of Combinatorial Theory, Series B. — 1983. — Т. 35, вып. 1. — С. 39—61. — doi:10.1016/0095-8956(83)90079-5..
  • Neil Robertson, Paul Seymour. Graph minors. XVI. Excluding a non-planar graph // Journal of Combinatorial Theory, Series B. — 2003. — Т. 89, вып. 1. — С. 43—76. — doi:10.1016/S0095-8956(03)00042-X..
  • Neil Robertson, Paul D. Seymour. Graph Minors. XX. Wagner's conjecture // Journal of Combinatorial Theory, Series B. — 2004. — Т. 92, вып. 2. — С. 325—357. — doi:10.1016/j.jctb.2004.08.001..
  • Petra Scheffler. Topics in Combinatorics and Graph Theory / R. Bodendiek, R. Henn. — Physica-Verlag, 1990. — С. 613—620..
  • Petra Scheffler. Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity / Jaroslav Nešetřil, Miroslav Fiedler. — Elsevier, 1992..
  • Konstantin Skodinis. Proc. 8th European Symposium on Algorithms (ESA 2000). — Springer-Verlag, 2000. — Т. 1879. — С. 403—414. — (Lecture Notes in Computer Science). — ISBN 978-3-540-41004-1. — doi:10.1007/3-540-45253-2_37..
  • Konstantin Skodinis. Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time // Journal of Algorithms. — 2003. — Т. 47, вып. 1. — С. 40—59. — doi:10.1016/S0196-6774(02)00225-0..
  • Karol Suchan, Ioan Todinca. Proc. 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007). — Springer-Verlag, 2007. — Т. 4769. — С. 258—269. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-74839-7_25..
  • Matthew Suderman. Pathwidth and layered drawings of trees // International Journal of Computational Geometry and Applications. — 2004. — Т. 14, вып. 3. — С. 203—225. — doi:10.1142/S0218195904001433. Архивировано 3 мая 2003 года..
  • Atsushi Takahashi, Shuichi Ueno, Yoji Kajitani. Minimal acyclic forbidden minors for the family of graphs with bounded path-width // Discrete Mathematics. — 1994. — Т. 127, вып. 1—3. — С. 293—304. — doi:10.1016/0012-365X(94)90092-2..
  • Ф.В. Фомин. Задачи преследования и поиска на графах // Электронная библиотека диссертаций. — 1996.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.