Ширина пути

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

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

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

Определение

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

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

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

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

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

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

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

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

Декомпозиция путей может быть описана как последовательность графов Gi _, которые склеены вместе путем идентификации пар вершин из последовательных графов в последовательности, так что результатом выполнения всех этих склеек является G . Графы G _i можно рассматривать как индуцированные подграфы множеств X _i в первом определении разложения путей, причем две вершины в последовательных индуцированных подграфах склеиваются вместе, когда они индуцированы одной и той же вершиной в G и в другом направлении. можно восстановить множества X _i как множества вершин графов G _i . Тогда ширина разложения пути будет на единицу меньше максимального числа вершин в одном из графов G _i .

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

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

Ширина пути любого графа G равна на единицу меньше, чем наименьшее кликовое число интервального графа , содержащего G в качестве подграфа. То есть для каждого разложения путей 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. пути Это следует из ранее полученной эквивалентности с кликовыми числами интервального графа: если 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 -пути. В частности, максимальные графы с шириной пути один являются в точности деревьями-гусеницами .

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

Любой n -вершинный лес имеет ширину пути O (log n ) . Ведь в лесу всегда можно найти постоянное число вершин, удаление которых дает лес, который можно разделить на два меньших подлеса с не более чем По 2 н ⁄ 3 вершины. Линейная структура, образованная путем рекурсивного разделения каждого из этих двух подлесов с размещением разделяющих вершин между ними, имеет логарифмическое число поиска вершин. Тот же метод, примененный к древовидной декомпозиции графа, показывает, что если ширина дерева n -вершинного графа G равна t , то ширина пути G равна O ( t log n ) . Поскольку внешнепланарные графы , последовательно-параллельные графы и графы Халина имеют ограниченную ширину дерева, все они также имеют не более чем логарифмическую ширину пути.

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

В любом плоском графе ширина пути не более чем пропорциональна квадратному корню из числа вершин. Один из способов найти разложение путей с такой шириной — (аналогично описанному выше разложению путей по логарифмической ширине) использовать теорему о плоском сепараторе, чтобы найти набор из O ( √ n ) вершин, удаление которых разделяет разбить граф на два подграфа не более 2 n ⁄ 3 вершины в каждой и объединить рекурсивно построенные разложения путей для каждого из этих двух подграфов. Тот же метод применим к любому классу графов, для которого справедлива аналогичная теорема о сепараторе. Поскольку, как и планарные графы, графы в любом фиксированном минорно-замкнутом семействе графов имеют разделители размера O ( √ n ) , отсюда следует, что ширина пути графов в любом фиксированном минорно-замкнутом семействе снова равна O ( √ n ) . Для некоторых классов планарных графов ширина пути графа и ширина пути его двойственного графа должны отличаться друг от друга в пределах постоянного коэффициента: границы этой формы известны для двусвязных внешнепланарных графов. и для многогранных графов. Для 2-связных плоских графов ширина пути двойственного графа меньше ширины пути линейного графа. Остается открытым вопрос, всегда ли в остальных случаях ширина пути плоского графа и его двойника находится в пределах постоянного коэффициента друг друга.

В некоторых классах графов доказано, что ширина пути и ширина дерева всегда равны друг другу: это справедливо для кографов , графы перестановок , дополнения ​ графов сравнимости , и графики сравнимости интервальных порядков .

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

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

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

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

Вычисление разложения путей

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

Управляемость с фиксированными параметрами

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

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

Бодлендер (1994) исследует сложность вычисления ширины пути на различных специальных классах графов. ли ширина пути графа G Определение того , превышает k, остается NP-полным, когда G ограничен графами ограниченной степени, плоские графы , плоские графы ограниченной степени, хордальные графы , хордовое домино, дополнения ​ графов сравнимости , и двудольные дистанционно-наследственные графы . Отсюда сразу следует, что он также NP-полен для семейств графов, содержащих двудольные дистанционно-наследственные графы, включая двудольные графы, хордальные двудольные графы, дистанционно-наследственные графы и круговые графы .

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

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

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

Миноры графа

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

Исключая лес

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

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

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

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

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

Хотя X _p обязательно включает в себя хотя бы один лес, неверно, что все графы в X _p являются лесами: например, X ₁ состоит из двух графов, семивершинного дерева и треугольника K ₃ . Однако множество деревьев из X _p можно точно охарактеризовать: эти деревья являются в точности теми деревьями, которые можно образовать из трех деревьев из X _{p − 1,} соединив новую корневую вершину ребром с произвольно выбранной вершиной в каждом из три маленьких дерева. Например, дерево с семью вершинами в X ₁ формируется таким образом из дерева с двумя вершинами (одним ребром) в X ₀ . На основании этой конструкции можно показать, что число запрещенных миноров в X _p не менее ( p !) ² . Полный набор X ₂ запрещенных миноров для графов с шириной пути 2 был вычислен; он содержит 110 различных графиков.

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

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

Приложения

СБИС

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

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

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

Рисование графика

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

• Минимальные графы с заданным числом пересечений имеют ширину пути, ограниченную функцией числа пересечений.
• Количество параллельных линий, на которых вершины дерева могут быть нарисованы без пересечения ребер (при различных естественных ограничениях на способы размещения соседних вершин относительно последовательности линий), пропорционально ширине пути дерева.
• Рисунок с k -пересечением h графа G -слоя представляет собой размещение вершин G на h различных горизонтальных линиях с ребрами, проложенными как монотонные ломаные пути между этими линиями, таким образом, что существует не более k пересечений. Графы с такими рисунками имеют ширину пути, ограниченную функцией h и k . Следовательно, когда h и k оба постоянны, можно за линейное время определить, имеет ли граф рисунок k -пересекающегося h -слоя.
• Граф с n вершинами и шириной пути p можно встроить в трехмерную сетку размером p × p × n таким образом, чтобы никакие два ребра (представленные в виде отрезков прямых между точками сетки) не пересекали друг друга. Таким образом, графы ограниченной ширины путей имеют вложения этого типа с линейным объемом.

Дизайн компилятора

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

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

Лингвистика

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

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

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

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

См. также

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

Ссылки

• Алон, Нога ; Сеймур, Пол ; Томас, Робин (1990), «Теорема о разделителе для графов с исключенным минором и ее приложения», Proc. 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 Journal on Algebraic and Discrete Methods , 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 .
• Бодлендер, Ханс Л. (1994), «Туристический гид по ширине деревьев», в Дассове, Юрген; Келеменова, Алиса (ред.), Развитие теоретической информатики (Труды 7-го Международного собрания молодых ученых-компьютерщиков, Смоленице, 16–20 ноября 1992 г.) , Темы компьютерной математики, том. 6, Гордон и Брич, стр. 1–20 .
• Бодлендер, Ханс Л. (1994a). «Туристический путеводитель по ширине деревьев». Акта Кибернетика . 11 : 1–2.
• Бодлендер, Ханс Л. (1996), «Алгоритм линейного времени для поиска разложений деревьев небольшой ширины», SIAM Journal on Computing , 25 (6): 1305–1317, doi : 10.1137/S0097539793251219 , hdl : 1874/16670 .
• Бодлендер, Ханс Л. (1998), «Частичный k -дендрарий графов с ограниченной шириной дерева», Theoretical Computer Science , 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 .
• Бодлендер, Ханс Л .; Гилберт, Джон Р.; Хафштейнссон, Хьялмтир; Клокс, Тон (1992), «Аппроксимация ширины дерева, ширины пути и минимальной высоты дерева исключения», Теоретико-графовые концепции в информатике , Конспекты лекций по информатике , том. 570, стр. 1–12, doi : 10.1007/3-540-55121-2_1 , hdl : 1874/17927 , ISBN  978-3-540-55121-8 .
• Бодлендер, Ганс Л .; Гуштедт, Йенс; Телле, Ян Арне (1998), «Распределение регистров в линейном времени для фиксированного количества регистров», Proc. 9-й симпозиум ACM – SIAM по дискретным алгоритмам (SODA '98) (PDF) , стр. 574–583 .
• Бодлендер, Ханс Л .; Клокс, Тон (1996), «Эффективные и конструктивные алгоритмы для определения ширины пути и ширины дерева графов», Journal of Algorithms , 21 (2): 358–402, doi : 10.1006/jagm.1996.0049 , hdl : 1874/16538 .
• Бодлендер, Ганс Л .; Клокс, Тон; Крач, Дитер (1993), "Ширина дерева и ширина пути графов перестановок", Proc. 20-й Международный коллоквиум по автоматам, языкам и программированию (ICALP 1993) , Конспекты лекций по информатике, том. 700, Springer-Verlag, стр. 114–125, doi : 10.1007/3-540-56939-1_66 , hdl : 1874/16657 , ISBN  978-3-540-56939-8 .
• Бодлендер, Ханс Л .; Мёринг, Рольф Х. (1990), "Ширина пути и ширина дерева кографов", Proc. 2-й скандинавский семинар по теории алгоритмов , Конспекты лекций по информатике, том. 447, Springer-Verlag, стр. 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: краткое доказательство теоремы о ширине пути», Combinatorics, Probability and Computing , 4 (1): 27–30, doi : 10.1017/S0963548300001450 .
• Дистель, Рейнхард; Кюн, Даниэла (2005), «Минорные иерархии графов», Дискретная прикладная математика , 145 (2): 167–182, doi : 10.1016/j.dam.2004.01.010 .
• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги ; Каварабаяши, Кен-ичи (2005), «Меньшая теория алгоритмических графов: декомпозиция, аппроксимация и раскраска», Proc. 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-Х .
• Дуймович, В. ; Товарищи, MR ; Китчинг, М.; Лиотта, Г.; Маккартин, К.; Нисимура, Н.; Рагде, П.; Розамонд, Ф.; Уайтсайдс, С. ; Вуд, Дэвид Р. (2008), «О параметризованной сложности построения многослойных графов», Algorithmica , 52 (2): 267–292, doi : 10.1007/s00453-007-9151-1 , S2CID   2298634 .
• Дуймович, Вида ; Морен, Пэт ; Вуд, Дэвид Р. (2003), «Ширина пути и трехмерные чертежи графиков с прямой сеткой» (PDF) , Proc. 10-й Международный симпозиум по рисованию графов (GD 2002) , Конспекты лекций по информатике, том. 2528, Springer-Verlag, стр. 42–53 .
• Эллис, Дж.А.; Садборо, Айдахо; Тернер, Дж. С. (1983), «Разделение графов и число поиска», Proc. 1983 Аллертонская конференция. по связи, управлению и вычислениям . Цитируется Мониеном и Садборо (1988) .
• Эллис, Дж.А.; Садборо, Айдахо; Тернер, Дж. С. (1994), «Разделение вершин и число поиска в дереве», Information and Computation , 113 (1): 50–79, doi : 10.1006/inco.1994.1064 .
• Файги, Уриэль ; Хаджиагайи, Мохаммадтаги ; Ли, Джеймс Р. (2005), «Улучшенные алгоритмы аппроксимации вершинных разделителей минимального веса», Proc. 37-й симпозиум ACM по теории вычислений (STOC 2005) , стр. 563–572, doi : 10.1145/1060590.1060674 , ISBN  1581139608 , S2CID   14097859 .
• Товарищи, Майкл Р .; Лэнгстон, Майкл А. (1989), «О поисковых решениях и эффективности алгоритмов с полиномиальным временем», Proc. 21-й симпозиум ACM по теории вычислений , стр. 501–512, doi : 10.1145/73007.73055 , ISBN  0897913078 , S2CID   1854173 .
• Феррейра, Афонсу Дж.; Сонг, Сян В. (1992), «Достижение оптимальности компоновки вентильной матрицы и свертывания PLA: подход теории графов», Proc. 1-й Латиноамериканский симпозиум по теоретической информатике (LATIN '92) , Конспекты лекций по информатике, том. 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) 24 июля 2011 г. , получено 6 мая 2010 г.
• Фомин, Федор В. (2003), «Ширина плоских и линейных графов», Graphs and Combinatorics , 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), «О самодвойственности ширины пути в вложениях многогранных графов», Journal of Graph Theory , 55 (1): 42–54, doi : 10.1002/jgt.20219 .
• Гарбе, Ренате (1995), "Ширина дерева и ширина пути графов сравнимости интервальных порядков", Proc. 20-й международный семинар по теоретико-графовым концепциям в информатике (WG'94) , Конспекты лекций по информатике, том. 903, Springer-Verlag, стр. 26–37, номер документа : 10.1007/3-540-59071-4_35 , ISBN.  978-3-540-59071-2 .
• Головач, П.А. (1993), «Ширина графа и число разделения вершин линейного графа», Discrete Mathematics and Applications , 3 (5): 517–522, doi : 10.1515/dma.1993.3.5.517 , S2CID   120745961 .
• Гуха, Судипто (2000), «Алгоритмы разделения вложенных графов и аппроксимации», Proc. 41-й симпозиум IEEE по основам информатики (FOCS 2000) , стр. 126, номер домена : 10.1109/SFCS.2000.892072 , ISBN  0-7695-0850-2 , S2CID   9854056 .
• Гурски, Фрэнк; Ванке, Эгон (2007), «Линейные графики ограниченной ширины клики», Discrete Mathematics , 307 (22): 2734–2754, doi : 10.1016/j.disc.2007.01.020 .
• Густедт, Йенс (1993), «О ширине хордальных графов», Discrete Applied Mathematics , 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-полнота проблемы поиска графа интервалов с минимальным числом клик, содержащего данный граф в качестве подграфа», Proc. Международный симпозиум по схемам и системам , стр. 657–660 .
• Кинерсли, Нэнси Г. (1992), «Число разделения вершин графа равно ширине его пути», Information Processing Letters , 42 (6): 345–350, doi : 10.1016/0020-0190(92)90234-M .
• Кинерсли, Нэнси Г.; Лэнгстон, Майкл А. (1994), «Изоляция множества препятствий для задачи компоновки матрицы вентилей», Discrete Applied Mathematics , 54 (2–3): 169–213, doi : 10.1016/0166-218X(94)90021-3 .
• Кирусис, Лефтерис М.; Пападимитриу, Христос Х. (1985), «Интервальные графики и поиск» (PDF) , Discrete Mathematics , 55 (2): 181–184, doi : 10.1016/0012-365X(85)90046-9 , заархивировано из оригинала ( PDF) от 21 июля 2011 г.
• Клокс, Тон; Бодлендер, Ханс Л. (1992), "Аппроксимация ширины дерева и ширины пути некоторых классов совершенных графов", Proc. 3-й Международный симпозиум по алгоритмам и вычислениям (ISAAC'92) , Конспекты лекций по информатике, том. 650, Springer-Verlag, стр. 116–125, doi : 10.1007/3-540-56279-6_64 , hdl : 1874/16672 , ISBN  978-3-540-56279-5 .
• Клокс, Т.; Бодлендер, Х. ; Мюллер, Х.; Крач, Д. (1993), «Вычисление ширины дерева и минимального заполнения: все, что вам нужно, это минимальные разделители», Proc. 1-й Европейский симпозиум по алгоритмам (ESA'93) (Конспекты лекций по информатике) , том. 726, Springer-Verlag, стр. 260–271, номер документа : 10.1007/3-540-57273-2_61 .
• Клокс, Тон; Крач, Дитер; Мюллер, Х. (1995), «Домино», Proc. 20-й международный семинар по теоретико-графовым концепциям в информатике (WG'94) , Конспекты лекций по информатике, том. 903, Springer-Verlag, стр. 106–120, номер документа : 10.1007/3-540-59071-4_41 , ISBN.  978-3-540-59071-2 .
• Кнейс, Иоахим; Мёлле, Даниэль; Рихтер, Стефан; Россманит, Питер (2005), «Алгоритмы, основанные на древовидной ширине разреженных графов», Proc. 31-й международный семинар по теоретико-графовым концепциям в информатике (WG 2005) , Конспекты лекций по информатике, том. 3787, Springer-Verlag, стр. 385–396, номер документа : 10.1007/11604686_34 , ISBN.  978-3-540-31000-6 .
• Корах, Ефрем; Солель, Нир (1993), «Ширина дерева, ширина пути и ширина разреза», Discrete Applied Mathematics , 43 (1): 97–101, doi : 10.1016/0166-218X(93)90171-J .
• Корнаи, Андраш; Туза, Жолт (1992), «Узкость, ширина пути и их применение в обработке естественного языка», Discrete Applied Mathematics , 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, Бибкод : 1980ITED...27.1671L , doi : 10.1109 /T-ED.1980.20086 , S2CID   64469353 , также в совместном выпуске IEEE Journal of Solid-State Circuits 15 (4): 736–740, 1980 .
• Миллер, Джордж А. (1956), «Магическое число семь, плюс-минус два» , Psychoological Review , 63 (2): 81–97, doi : 10.1037/h0043158 , hdl : 11858/00-001M-0000-002C -4646-Б , ПМИД   13310704 .
• Мёринг, Рольф Х. (1990), «Проблемы с графами, связанные с компоновкой вентильной матрицы и складыванием PLA», в Tinhofer, G.; Майр, Э.; Нольтемайер, Х.; и др. (ред.), Вычислительная теория графов , Computing Supplementum, vol. 7, Springer-Verlag, стр. 17–51, ISBN.  3-211-82177-5 .
• Моньен, Б.; Садборо, Айленд (1988), «Минимальный разрез является NP-полным для деревьев, взвешенных по ребрам», Theoretical Computer Science , 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 .
• Пэн, Шэн-Лунг; Хо, Чин-Вэнь; Сюй, Цань-шэн; Ко, Минг-Тат; Тан, Чуан И (1998), «Алгоритм линейного времени для построения оптимальной стратегии поиска узлов дерева», в Сюй, Вэнь-Лянь; Као, Мин-Ян (ред.), Вычисления и комбинаторика, 4-я ежегодная международная конференция, COCOON '98, Тайбэй, Тайвань, Китай, 12–14 августа 1998 г., Труды , конспекты лекций по информатике, том. 1449, Спрингер, стр. 279–288, номер документа : 10.1007/3-540-68535-9_32.
• Проскуровский, Анджей; Телле, Ян Арне (1999), «Классы графов с моделями с ограниченными интервалами» (PDF) , Дискретная математика и теоретическая информатика , 3 : 167–176 .
• Робертсон, Нил ; Сеймур, Пол (1983), «Минорные графы. I. Исключение леса», Журнал комбинаторной теории, серия B , 35 (1): 39–61, doi : 10.1016/0095-8956(83)90079-5 .
• Робертсон, Нил ; Сеймур, Пол (2003), «Минорные графы. XVI. Исключение непланарного графа», Journal of Combinatorial Theory, Series B , 89 (1): 43–76, doi : 10.1016/S0095-8956(03)00042- Х. ​
• Робертсон, Нил ; Сеймур, Пол Д. (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) , Конспекты лекций по информатике, том. 1879, Springer-Verlag, стр. 403–414, номер документа : 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 .
• Сучан, Кароль; Тодинка, Иоан (2007), «Ширина графов дуг окружности», Proc. 33-й международный семинар по теоретико-графовым концепциям в информатике (WG 2007) , Конспекты лекций по информатике, том. 4769, Springer-Verlag, стр. 258–269, номер документа : 10.1007/978-3-540-74839-7_25 .
• Судерман, Мэтью (2004), «Ширина путей и слоистые рисунки деревьев» (PDF) , Международный журнал вычислительной геометрии и приложений , 14 (3): 203–225, doi : 10.1142/S0218195904001433 , заархивировано из оригинала (PDF) на 3 мая 2003 г.
• Такахаши, Ацуши; Уэно, Шуичи; Кадзитани, Йоджи (1994), «Минимальные ациклические запрещенные миноры для семейства графов с ограниченной шириной пути», Discrete Mathematics , 127 (1–3): 293–304, doi : 10.1016/0012-365X(94)90092- 2 .
• Вигерс, Манфред (1990), «Вложения графов (теорема 5.2)», Из докторской диссертации Uni-GH Paderborn : 1–76, doi : 10.13140/RG.2.2.27153.65124 .