Ширина пути - Pathwidth

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

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

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

Определение

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

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

  1. Для каждого края грамм, существует я такие, что оба конца ребра принадлежат подмножеству Икся, и
  2. Для каждых трех индексов я ≤ j ≤ k, Икся ∩ Иксk ⊆ Иксj.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Границы

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

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

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

Любой п-вертекс лес имеет ширину пути O (журналп).[18] Ведь в лесу всегда можно найти постоянное количество вершин, удаление которых оставляет лес, который можно разделить на два меньших подлеса с не более чем двумяп/ 3 вершины каждая. Линейная структура, образованная рекурсивным разделением каждого из этих двух подлесов с размещением разделяющих вершин между ними, имеет логарифмическое число поиска вершин. Тот же метод, примененный к древовидной декомпозиции графа, показывает, что если ширина дерева п-вершинный граф грамм является т, то ширина пути грамм это O (т бревноп).[19] С внешнепланарные графы, последовательно-параллельные графы, и Графики Халина все имеют ограниченную ширину дерева, все они также имеют логарифмическую ширину пути.

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

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

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

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Какова максимально возможная ширина пути -вертекс кубический граф ?
(больше нерешенных задач по математике)

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

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

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

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

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

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

Бодлендер (1994) исследует сложность вычисления ширины пути на различных специальных классах графов. Определение того, является ли ширина пути графа грамм самое большее k остается NP-полным, когда грамм ограничивается графами ограниченной степени,[35] планарные графы,[35] плоские графы ограниченной степени,[35] хордовые графы,[36] хордовые домино,[37] то дополняет из графики сопоставимости,[30]и двудольный дистанционно-наследственные графы.[38] Отсюда сразу следует, что он также является NP-полным для семейств графов, содержащих двудольные графы с дистанционной наследственностью, включая двудольные графы, хордовые двудольные графы, дистанционно наследственные графы и круговые графики.[38]

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

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

NP-сложно аппроксимировать ширину пути графа с точностью до аддитивной константы.[6]Самый известный коэффициент аппроксимации алгоритма полиномиального приближения для ширины пути O ((logп)3/2).[42]Для более ранних алгоритмов приближения для ширины пути см. Bodlaender et al. (1992) и Гуха (2000). По поводу приближений на ограниченных классах графов см. Клокс и Бодлендер (1992).

График миноров

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

Исключая лес

Если семья F графов закрывается при взятии несовершеннолетних (каждый несовершеннолетний члена F также в F), то по Теорема Робертсона – Сеймура F можно охарактеризовать как графы, не имеющие Икс, куда Икс конечный набор запрещенные несовершеннолетние.[43] Например, Теорема Вагнера заявляет, что планарные графы являются графами, не имеющими полный график K5 ни полный двудольный граф K3,3 как несовершеннолетние. Во многих случаях свойства F и свойства Икс тесно связаны, и первый результат такого рода был сделан Робертсон и Сеймур (1983),[2] и связывает ограниченную ширину пути с существованием лес в семье запрещенных несовершеннолетних. В частности, определите семью F графиков иметь ограниченная ширина пути если существует постоянная п такой, что каждый граф в F имеет пропускную способность не более п. Потом несовершеннолетняя замкнутая семья F имеет ограниченную пропускную способность тогда и только тогда, когда набор Икс запрещенных несовершеннолетних для F включает как минимум один лес.

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

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

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

Свойство иметь максимальную пропускную способность п само закрыто на прием несовершеннолетних: если грамм имеет разложение по пути шириной не более п, то такое же разбиение по путям остается в силе, если из грамм, а любую вершину можно удалить из грамм и от его разложения по траектории без увеличения ширины. Сжатие кромки также может быть выполнено без увеличения ширины разложения путем слияния подпутей, представляющих две конечные точки суженной кромки. Следовательно, графики пропускной способности не более п можно охарактеризовать набором Иксп исключенных несовершеннолетних.[43][45]

Несмотря на то что Иксп обязательно включает в себя хотя бы один лес, неверно, что все графы в Иксп леса: например, Икс1 состоит из двух графов, дерева с семью вершинами и треугольника K3. Однако набор деревьев в Иксп можно точно охарактеризовать: эти деревья - именно те деревья, которые могут быть образованы из трех деревьев в Иксп − 1 путем соединения новой корневой вершины ребром с произвольно выбранной вершиной в каждом из трех меньших деревьев. Например, дерево с семью вершинами в Икс1 формируется таким образом из двухвершинного дерева (одного ребра) в Икс0. Исходя из этой конструкции, количество запрещенных несовершеннолетних в Иксп можно показать как минимум (п!)2.[45] Полный комплект Икс2 вычислено запрещенных миноров для графов с шириной пути-2; он содержит 110 различных графиков.[46]

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

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

Приложения

СБИС

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

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

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

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

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

  • Минимальные графы с заданным номер перехода имеют пропускную способность, ограниченную функцией их числа пересечений.[52]
  • Количество параллельных линий, на которых вершины дерева могут быть нарисованы без пересечения ребер (при различных естественных ограничениях на способы размещения смежных вершин относительно последовательности линий), пропорционально ширине пути дерева.[53]
  • А k-кроссинг час-слойное рисование графика грамм размещение вершин грамм на час четкие горизонтальные линии, края которых проложены как монотонные многоугольные пути между этими линиями таким образом, чтобы k переходы. Графики с такими рисунками имеют ширину пути, ограниченную функцией час и k. Следовательно, когда час и k оба постоянны, можно за линейное время определить, имеет ли граф k-кроссинг час-слойный рисунок.[54]
  • График с п вершины и ширина пути п может быть встроен в трехмерную сетку размером п × п × п таким образом, чтобы никакие два ребра (представленные отрезками прямых линий между точками сетки) не пересекались друг с другом. Таким образом, графы с ограниченной шириной пути имеют вложения этого типа с линейным объемом.[55]

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

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

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

Лингвистика

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

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

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

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

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

  • Токсичность, другой способ измерения сложности произвольного графа в терминах интервальных графов
  • Глубина дерева, число, которое является ограниченным для семейства минорно-замкнутых графов тогда и только тогда, когда семейство исключает путь
  • Вырождение, мера разреженности графа, которая не более чем равна ширине его пути
  • Пропускная способность графика, другая задача NP-полной оптимизации с использованием линейных схем графов
  • Номер Strahler, мера сложности корневых деревьев, определяемая аналогично ширине пути некорневых деревьев

Примечания

  1. ^ Дистель и Кюн (2005).
  2. ^ а б c d Робертсон и Сеймур (1983).
  3. ^ Бодлендер (1998).
  4. ^ а б Робертсон и Сеймур (2003).
  5. ^ а б Касивабара и Фудзисава (1979); Ohtsuki et al. (1979); Ленгауэр (1981); Арнборг, Корнейл и Проскуровски (1987).
  6. ^ а б Bodlaender et al. (1992).
  7. ^ а б c Бодлендер (1996); Бодлендер и Клокс (1996)
  8. ^ Бодлендер (1994).
  9. ^ а б Меринг (1990); Шеффлер (1990); Эллис, Садборо и Тернер (1994); Peng et al. (1998); Скодинис (2000); Скодинис (2003); Кудерт, Хук и Мазурик (2012).
  10. ^ а б Арнборг (1985).
  11. ^ а б Аспвалл, Проскуровски и Телле (2000).
  12. ^ Бодлендер, Ханс Л. (1994). «Путеводитель по деревьям». Acta Cybernetica. 11: 1–2.
  13. ^ Бодлендер (1998), Теорема 29, с. 13.
  14. ^ Киннерсли (1992); Бодлендер (1998), Теорема 51.
  15. ^ Проскуровский и Телле (1999).
  16. ^ Корах и Солел (1993), Лемма 3 с.99; Бодлендер (1998), Теорема 47, с. 24.
  17. ^ Корах и Солел (1993), Лемма 1, с. 99; Бодлендер (1998), Теорема 49, с. 24.
  18. ^ Корах и Солел (1993), Теорема 5, с. 99; Бодлендер (1998), Теорема 66, с. 30. Шеффлер (1992) дает более точную верхнюю границу журнала3(2п + 1) на ширине пути п-верхний лес.
  19. ^ Корах и Солел (1993), Теорема 6, с. 100; Бодлендер (1998), Следствие 24, стр.10.
  20. ^ Гурски и Ванке (2007).
  21. ^ Головач (1993).
  22. ^ Бодлендер (1998), Следствие 23, с. 10.
  23. ^ Бодлендер (1998), Теорема 20, с. 9.
  24. ^ Алон, Сеймур и Томас (1990).
  25. ^ Бодлендер и Фомин (2002); Кудерт, Хук и Серени (2007).
  26. ^ Фомин и Тиликос (2007); Амини, Хюк и Перенн (2009).
  27. ^ Фомин (2003).
  28. ^ а б Бодлендер и Меринг (1990).
  29. ^ а б Бодлендер, Клокс и Крач (1993).
  30. ^ а б Хабиб и Меринг (1994).
  31. ^ а б Гарбе (1995).
  32. ^ а б c d Фомин и Хёй (2006).
  33. ^ Фомин и др. (2008).
  34. ^ Дауни и товарищи (1999), стр.12.
  35. ^ а б c d Моньен и Садборо (1988).
  36. ^ Густедт (1993).
  37. ^ Клокс, Крач и Мюллер (1995). Хордальное домино - это хордовый граф, в котором каждая вершина принадлежит не более чем двум максимальным кликам.
  38. ^ а б Kloks et al. (1993).
  39. ^ Клокс и Бодлендер (1992); Густедт (1993).
  40. ^ Гарбе (1995) приписывает этот результат доктору философии 1993 г. диссертация Тона Клокса; Алгоритм полиномиального времени Гарбе для графов сравнимости интервальных порядков обобщает этот результат, так как любой хордовый граф должен быть графом сопоставимости этого типа.
  41. ^ Сучан и Тодинка (2007).
  42. ^ Файги, Хаджиагайи и Ли (2005).
  43. ^ а б Робертсон и Сеймур (2004).
  44. ^ Bienstock et al. (1991); Дистель (1995); Кеттелл, Dinneen & Fellows (1996).
  45. ^ а б Киннерсли (1992); Такахаши, Уэно и Каджитани (1994); Бодлендер (1998), п. 8.
  46. ^ Киннерсли и Лэнгстон (1994).
  47. ^ Демейн, Хаджиагайи и Каварабаяши (2005).
  48. ^ Берже (1967).
  49. ^ Лопес и Закон (1980).
  50. ^ а б Товарищи и Лэнгстон (1989).
  51. ^ Меринг (1990); Феррейра и песня (1992).
  52. ^ Глинены (2003).
  53. ^ Судерман (2004).
  54. ^ Дуймович и др. (2008).
  55. ^ Дуймович, Morin & Wood (2003).
  56. ^ а б Бодлендер, Густедт и Телле (1998).
  57. ^ Миллер (1956).
  58. ^ Kneis et al. (2005); Бьёрклунд и Хусфельдт (2008).

Рекомендации