Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Определение [ править ]

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

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

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

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

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

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

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

Последовательности склеивания [ править ]

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

Толщина интервала [ править ]

Граф интервалов с pathwidth два, один меньше , чем мощность четырех его максимальных клик АВС , ACD , CDE и CDF .

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

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

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

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

Число разделения вершин [ править ]

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

Номер поиска узла [ править ]

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

Границы [ править ]

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

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

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

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

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

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

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

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

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

(больше нерешенных задач по математике)

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

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

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

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

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

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

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

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

Алгоритмы аппроксимации [ править ]

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

График миноры [ править ]

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

Исключение леса [ править ]

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

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

Препятствия для ограниченной пропускной способности [ править ]

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

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

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

Теория структуры [ править ]

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

Приложения [ править ]

СБИС [ править ]

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

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

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

Рисование графика [ править ]

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

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

Дизайн компилятора [ править ]

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

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

Лингвистика [ править ]

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

  1. ^ Diestel & Кюн (2005) .
  2. ^ а б в г Робертсон и Сеймур (1983) .
  3. ^ Bodlaender (1998) .
  4. ^ a b Робертсон и Сеймур (2003) .
  5. ^ a b Кашивабара и Фудзисава (1979) ; Ohtsuki et al. (1979) ; Ленгауэр (1981) ; Арнборг, Корнейл и Проскуровски (1987) .
  6. ^ a b Bodlaender et al. (1992) .
  7. ^ a b c Бодлендер (1996) ; Бодлендер и Клокс (1996)
  8. ^ Bodlaender (1994) .
  9. ^ а б Меринг (1990) ; Шеффлер (1990) ; Эллис, Садборо и Тернер (1994) ; Peng et al. (1998) ; Скодинис (2000) ; Скодинис (2003) ; Coudert, Huc и Mazauric (2012) .
  10. ^ а б Арнборг (1985) .
  11. ^ а б Аспвалл, Проскуровски и Телле (2000) .
  12. ^ Bodlaender, Ганс Л. (1994). «Путеводитель по ширине деревьев». Acta Cybernetica . 11 : 1-2.
  13. ^ Bodlaender (1998) , теорема 29, стр. 13.
  14. ^ Киннерсли (1992) ; Бодлендер (1998) , теорема 51.
  15. ^ Proskurowski & Telle (1999) .
  16. ^ Корах & Solel (1993) , с.99 лемму 3; Бодлендер (1998) , теорема 47, стр. 24.
  17. ^ Корах & Solel (1993) , лемма 1, стр. 99; Бодлендер (1998) , теорема 49, стр. 24.
  18. ↑ Korach & Solel (1993) , теорема 5, стр. 99; Бодлендер (1998) , теорема 66, стр. 30. Шеффлер (1992) дает более точную верхнюю границу log 3 (2 n  + 1) для ширины путилесас n вершинами.
  19. ↑ Korach & Solel (1993) , теорема 6, с. 100; Bodlaender (1998) , следствие 24, стр.10.
  20. ^ Гурский и Ванке (2007) .
  21. ↑ Головач (1993) .
  22. ^ Bodlaender (1998) , следствие 23, стр. 10.
  23. ^ Bodlaender (1998) , теорема 20, стр. 9.
  24. ^ Алон, Сеймур и Томас (1990) .
  25. ^ Bodlaender и Фомина (2002) ; Кудерт, Хук и Серени (2007) .
  26. ↑ Fomin & Thilikos (2007) ; Амини, Хюк и Перенн (2009) .
  27. ↑ Фомин (2003) .
  28. ↑ a b Bodlaender & Möhring (1990) .
  29. ^ a b Bodlaender, Kloks & Kratsch (1993) .
  30. ^ а б Хабиб и Меринг (1994) .
  31. ^ а б Гарбе (1995) .
  32. ^ а б в г Fomin & Høie (2006) .
  33. ^ Фомин и др. (2008) .
  34. Перейти ↑ Downey & Fellows (1999) , p.12.
  35. ^ a b c d Моньен и Садборо (1988) .
  36. ^ Gustedt (1993) .
  37. ^ Kloks, Kratsch & Müller (1995) . Хордальное домино - это хордовый граф, в котором каждая вершина принадлежит не более чем двум максимальным кликам.
  38. ^ a b Kloks et al. (1993) .
  39. ^ Kloks & Bodlaender (1992) ; Густедт (1993) .
  40. ^ Гарб (1995) кредитов этот результат к Ph.D. 1993 диссертация Тона Клокса; Алгоритм полиномиального времени Гарбе для графов сопоставимости интервальных порядков обобщает этот результат, поскольку любой хордовый граф должен быть графом сопоставимости этого типа.
  41. ^ Suchan & Todinca (2007) .
  42. ^ Feige, Hajiaghayi & Lee (2005) .
  43. ^ a b Робертсон и Сеймур (2004) .
  44. ^ Bienstock et al. (1991) ; Дистель (1995) ; Кеттелл, Dinneen & Fellows (1996) .
  45. ^ а б Киннерсли (1992) ; Такахаши, Уэно и Каджитани (1994) ; Бодлендер (1998) , стр. 8.
  46. ^ Киннерслей & Langston (1994) .
  47. ^ Demaine, Hajiaghayi & Kawarabayashi (2005) .
  48. Перейти ↑ Berge (1967) .
  49. Перейти ↑ Lopez & Law (1980) .
  50. ^ a b Fellows & Langston (1989) .
  51. ^ Меринг (1990) ; Феррейра и песня (1992) .
  52. ^ Hliněny (2003) .
  53. ^ Suderman (2004) .
  54. ^ Дуймович и др. (2008) .
  55. ^ Дуймович, Морин & Wood (2003) .
  56. ^ a b Bodlaender, Gustedt & Telle (1998) .
  57. ^ Миллер (1956) .
  58. ^ Kneis et al. (2005) ; Бьёрклунд и Хусфельдт (2008) .

Ссылки [ править ]

  • Алон, Нога ; Сеймур, Пол ; Томас, Робин (1990), "Теорема о разделителе для графов с исключенным минором и ее приложения", Proc. 22-й ACM Symp. по теории вычислений (STOC 1990) , стр 293-299,. DOI : 10,1145 / 100216.100254 , ISBN 0897913612, S2CID  17521329.
  • Амини, Омид; Хук, Флориан; Pérennes, Stéphane (2009), "На пути ширины плоских графов", SIAM Journal по дискретной математике , 23 (3): 1311-1316, DOI : 10,1137 / 060670146.
  • Arnborg, Стефан (1985), "Эффективные алгоритмы для комбинаторных задач на графах с ограниченной разложимостью - обследованием", БИТ , 25 (1): 2-23, DOI : 10.1007 / BF01934985 , S2CID  122263659.
  • Арнборг, Стефан; Корнейл, Дерек Г .; Proskurowski, Анджей (1987), "Сложность нахождения вложения в K -tree", SIAM журнал на алгебраических и дискретных методов , 8 (2): 277-284, DOI : 10,1137 / 0608024.
  • Аспвалл, Бенгт; Проскуровский, Анджей; Telle, Ян Арне (2000), "Требования к памяти для табличных вычислений в частичном K -tree алгоритмов", 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.
  • Бьёрклунд, Андреас; Husfeldt, Thore (2008), "Точные алгоритмы для точной выполнимости и числа совершенных паросочетаний", Algorithmica , 52 (2): 226-249, DOI : 10.1007 / s00453-007-9149-8 , S2CID  37693881.
  • Бодландер, Ханс Л. (1994), «Путеводитель по деревьям», Дассов, Юрген; Келеменова, Алиса (ред.), Развитие теоретической информатики (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 ноября 1992 г.) , Topics in Computer Mathematics, 6 , Gordon and Breach, pp. 1–20.
  • Бодлендер, Ханс Л. (1996), «Алгоритм линейного времени для поиска разложения дерева с малой шириной дерева», SIAM Journal on Computing , 25 (6): 1305–1317, DOI : 10.1137 / S0097539793251219 , hdl : 1874/16670.
  • Бодлендер, Ханс Л. (1998), «Частичный k- арборетум графов с ограниченной древовидной шириной», Теоретическая информатика , 209 (1-2): 1–45, DOI : 10.1016 / S0304-3975 (97) 00228-4.
  • Bodlaender, Hans L .; Фомин, Федор В. (2002), "Аппроксимация ширины пути внешнепланарных графов", Журнал алгоритмов , 43 (2): 190–200, DOI : 10.1016 / S0196-6774 (02) 00001-9.
  • Bodlaender, Hans L .; Гилберт, Джон Р .; Хафстейнссон, Хьялмтыр; Kloks, Ton (1992), "Аппроксимация древесная ширина, pathwidth, и минимальная ликвидация высота дерева", Graph Теоретико-концепции в области компьютерных наук , Lecture Notes в области компьютерных наук , 570 , с 1-12. Дои : 10.1007 / 3-540- 55121-2_1 , hdl : 1874/17927 , ISBN 978-3-540-55121-8.
  • Bodlaender, Hans L .; Густедт, Йенс; Телле, Ян Арне (1998), "Линейное распределение регистров для фиксированного числа регистров", Proc. 9-й симпозиум ACM – SIAM по дискретным алгоритмам (SODA '98) (PDF) , стр. 574–583.
  • Bodlaender, Hans L .; Kloks, Тон (1996), "Эффективные и конструктивные алгоритмы pathwidth и древесная ширина графов", Journal алгоритмов , 21 (2): 358-402, DOI : 10,1006 / jagm.1996.0049 , ЛВП : 1874/16538.
  • Bodlaender, Hans L .; Клокс, Тон; Kratsch, Дитер (1993), "Ширина дерева и ширина пути графов перестановок", Proc. 20 -я Международная коллоквиум по автоматным, языкам и программированию (ICALP 1993) , Lecture Notes в области компьютерных наук, 700 , Springer-Verlag, стр 114-125,. Дои : 10.1007 / 3-540-56939-1_66 , ЛВП : 1874/16657 , ISBN 978-3-540-56939-8.
  • Bodlaender, Hans L .; Меринг, Рольф Х. (1990), "Ширина пути и ширина дерева кографов", Proc. Второй Скандинавский семинар по теории алгоритмов , Lecture Notes в области компьютерных наук, 447 ., Springer-Verlag, стр 301-309, DOI : 10.1007 / 3-540-52846-6_99 , ЛВП : 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.
  • Кудерт, Дэвид; Хук, Флориан; Mazauric, Дориан (2012), "Распределенная алгоритм вычисления узла поиска Количество в Trees" (PDF) , Algorithmica , 63 (1): 158-190, DOI : 10.1007 / s00453-011-9524-3.
  • Кудерт, Дэвид; Хук, Флориан; Серени, Жан-Себастьен (2007), «Ширина пути внешнепланарных графов» (PDF) , Журнал теории графов , 55 (1): 27–41, DOI : 10.1002 / jgt.20218.
  • Дистель, Рейнхард (1995), «Миноры графа I: краткое доказательство теоремы о ширине пути», Комбинаторика, вероятность и вычисления , 4 (1): 27–30, DOI : 10.1017 / S0963548300001450.
  • Дистель, Рейнхард; Кюн, Даниэла (2005), «Граф второстепенных иерархий», Дискретная прикладная математика , 145 (2): 167–182, DOI : 10.1016 / j.dam.2004.01.010.
  • Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги ; Каварабаяси, Кен-ичи (2005), "Алгоритмическая теория минор графов: декомпозиция, аппроксимация и раскраска", Proc. Сорок шестой IEEE симпозиум по Основы информатики (FOCS 2005) , стр 637-646,. Дои : 10,1109 / SFCS.2005.14 , ISBN 0-7695-2468-0, S2CID  13238254.
  • Дауни, Род Г .; Стипендиаты, Майкл Р. (1999), Параметризованная сложность , Springer-Verlag, ISBN 0-387-94883-X.
  • Dujmović, V .; Стипендиаты, MR ; Китчинг, М .; Liotta, G .; McCartin, C .; Nishimura, N .; Ragde, P .; Розамонд, Ф .; Whitesides, S .; Вуд, Дэвид Р. (2008), "О параметризованного сложности слоистого графа рисунка", Algorithmica , 52 (2): 267-292, DOI : 10.1007 / s00453-007-9151-1 , S2CID  2298634.
  • Дуймович, Вида; Morin, Pat ; Вуд, Дэвид Р. (2003), «Рисунки графиков с трехмерной прямой сеткой по ширине пути» (PDF) , Proc. 10-й Международный симпозиум по рисованию графиков (GD 2002) , конспект лекций по информатике, 2528 , Springer-Verlag, стр. 42–53..
  • Ellis, JA; Садборо, штат Айленд; Тернер, JS (1983), "Разделение графов и поиск числа", Proc. 1983 г., Allerton Conf. по связи, управлению и вычислениям. Цитируется Monien & Sudborough (1988) .
  • Ellis, JA; Садборо, штат Айленд; Тернер, Дж. С. (1994), "Разделение вершин и число поиска в дереве", Информация и вычисления , 113 (1): 50–79, DOI : 10.1006 / inco.1994.1064.
  • Файги, Уриил ; Хаджиагайи, Мохаммадтаги ; Ли, Джеймс Р. (2005), "Улучшенные алгоритмы аппроксимации для разделителей вершин минимального веса", Proc. Тридцать седьмой ACM симпозиум по теории вычислений (STOC 2005) , стр 563-572,. DOI : 10,1145 / 1060590.1060674 , ISBN 1581139608, S2CID  14097859.
  • Товарищи, Майкл Р .; Лэнгстон, Майкл А. (1989), "Решение поиска и эффективность алгоритмов с полиномиальным временем", Proc. Двадцать первый ACM симпозиум по теории вычислений ., Стр 501-512, DOI : 10,1145 / 73007,73055 , ISBN 0897913078, S2CID  1854173.
  • Ferreira, Afonso G .; Сонг, Сян В. (1992), «Достижение оптимальности для компоновки матрицы вентилей и сворачивания PLA: теоретико-графический подход», Proc. Первый Латиноамериканский симпозиум по теоретической информатике (LATIN '92) , Lecture Notes в области компьютерных наук, 583 , Springer-Verlag, стр 139-153,. DOI : 10.1007 / BFb0023825 , ЛВП : 10068/43314 , ISBN 3-540-55284-7.
  • де Флюитер, Бабетта (1997), Алгоритмы для графов малой ширины дерева (PDF) , Ph.D. диссертация, Утрехтский университет , ISBN 90-393-1528-0, заархивировано из оригинального (PDF) 24 июля 2011 г. , получено 06 мая 2010 г..
  • Фомин, Федор В. (2003), "Пропускная способность плоских и линейных графов", Графы и комбинаторика , 19 (1): 91–99, DOI : 10.1007 / s00373-002-0490-z , S2CID  43123449.
  • Фомин, Федор В .; Хойе, Кьяртан (2006), "Пропускная способность кубических графов и точные алгоритмы", Письма об обработке информации , 97 (5): 191–196, DOI : 10.1016 / j.ipl.2005.10.012.
  • Фомин, Федор В .; Крач, Дитер; Тодинка, Иоан; Villanger, Yngve (2008), "Точные алгоритмы древесной ширины и минимальной принудительную", SIAM журнал по вычислениям , 38 (3): 1058-1079, DOI : 10,1137 / 050643350 , ЛВП : 1956/1151.
  • Фомин, Федор В .; Тиликос, Димитриос М. (2007), "О самодуальности ширины пути в многогранных вложениях графов", Журнал теории графов , 55 (1): 42–54, DOI : 10.1002 / jgt.20219.
  • Гарбе, Ренате (1995), "Ширина дерева и ширина пути графов сопоставимости интервальных порядков", Proc. 20-й международный семинар «Теоретико-графические концепции в компьютерных науках» (WG'94) , Lecture Notes in Computer Science, 903 , Springer-Verlag, pp. 26–37, doi : 10.1007 / 3-540-59071-4_35 , ISBN 978-3-540-59071-2.
  • Головач, П.А. (1993), "Ширина разреза графа и число разделения вершин линейного графа", Дискретная математика и приложения , 3 (5): 517–522, doi : 10.1515 / dma.1993.3.5.517 , S2CID  120745961.
  • Гуха, Судипто (2000), "Алгоритмы разбиения и аппроксимации вложенных графов", Proc. 41-й симпозиум IEEE по основам компьютерных наук (FOCS 2000) , стр. 126, DOI : 10.1109 / SFCS.2000.892072 , ISBN 0-7695-0850-2, S2CID  9854056.
  • Гурски, Франк; Ванка, Эгон (2007), "Линейные графики ограниченных кликовым ширинов", Дискретная математика , 307 (22): 2734-2754, DOI : 10.1016 / j.disc.2007.01.020.
  • Густедт, Йенс (1993), «На пути хордовых графов», Дискретная прикладная математика , 45 (3): 233–248, DOI : 10.1016 / 0166-218X (93) 90012-D.
  • Хабиб, Мишель; Möhring, Rolf H. (1994), "древесная ширина от cocomparability графиков и новый порядок теоретико-параметр", Order , 11 (1): 47-60, DOI : 10.1007 / BF01462229 , S2CID  2648030.
  • Hliněny, Петр (2003), "Пересечение нумеровать критические графики имеют ограниченный путь ширины", Журнал комбинаторной теории, серии B , 88 (2): 347-367, DOI : 10.1016 / S0095-8956 (03) 00037-6.
  • Kashiwabara, T .; Fujisawa, T. (1979), "NP-полнота проблемы нахождения графа интервалов с минимальным числом кликов, содержащего данный граф в качестве подграфа", Proc. Международный симпозиум по схемам и системам , стр. 657–660..
  • Киннерсли, Нэнси Г. (1992), «Число разделения вершин графа равно его ширине пути», Письма об обработке информации , 42 (6): 345–350, DOI : 10.1016 / 0020-0190 (92) 90234-M.
  • Киннерсли, Нэнси Дж .; Лангстон, Майкл А. (1994), "Преграда набор изоляция для задачи компоновки ворот матрицы", Дискретная прикладная математика , 54 (2-3): 169-213, DOI : 10.1016 / 0166-218X (94) 90021-3.
  • Kirousis, Lefteris M .; Пападимитриу, Христос Х. (1985), «Интервальные графики и поиск» (PDF) , Дискретная математика , 55 (2): 181–184, DOI : 10.1016 / 0012-365X (85) 90046-9 , заархивировано из оригинала ( PDF) от 21.07.2011.
  • Клокс, Тон; Бодлендер, Ханс Л. (1992), "Аппроксимация ширины дерева и ширины пути некоторых классов совершенных графов", Proc. 3 - й Международный симпозиум по алгоритмам и вычислениям (ISAAC'92) , Lecture Notes в области компьютерных наук, 650 ., Springer-Verlag, стр 116-125, DOI : 10.1007 / 3-540-56279-6_64 , ЛВП : 1874/16672 , ISBN 978-3-540-56279-5.
  • Клокс, Т .; Bodlaender, H .; Müller, H .; Kratsch, D. (1993), "Вычисление ширины дерева и минимального заполнения: все, что вам нужно, это минимальные разделители", Proc. Первый европейский симпозиум по алгоритмам (ESA'93) (Lecture Notes в области компьютерных наук) , +726 ., Springer-Verlag, стр 260-271, DOI : 10.1007 / 3-540-57273-2_61.
  • Клокс, Тон; Крач, Дитер; Мюллер, Х. (1995), «Домино», Proc. 20-й международный семинар «Теоретико-графические концепции в компьютерных науках» (WG'94) , Lecture Notes in Computer Science, 903 , Springer-Verlag, pp. 106–120, doi : 10.1007 / 3-540-59071-4_41 , ISBN 978-3-540-59071-2.
  • Кнейс, Иоахим; Мёлле, Даниэль; Рихтер, Стефан; Россманиф, Питер (2005), "Алгоритмы, основанные на древовидной ширине разреженных графов", Proc. 31-й международный семинар по теоретико-графическим концепциям в компьютерных науках (WG 2005) , конспект лекций по компьютерным наукам, 3787 , Springer-Verlag, стр. 385–396, doi : 10.1007 / 11604686_34 , ISBN 978-3-540-31000-6.
  • Корах, Ефрем; Solel, Нир (1993), "Дерево ширина, путь ширина и Ширина разрез", Дискретная прикладная математика , 43 (1): 97-101, DOI : 10.1016 / 0166-218X (93) 90171-J ,.
  • Корнаи, Андраш; Туза, Жолт (1992), «Узость, ширина пути и их применение в обработке естественного языка», Дискретная прикладная математика , 36 (1): 87–92, DOI : 10.1016 / 0166-218X (92) 90208-R.
  • Lengauer, Томас (1981), "Черно-белые камешки и разделение графа", Acta Informatica , 16 (4): 465-475, DOI : 10.1007 / BF00264496 , S2CID  19415148.
  • Лопес, Александр Д .; Law, Hung-Fai S. (1980), "Метод компоновки матрицы с плотным затвором для MOS VLSI", IEEE Transactions on Electron Devices , ED-27 (8): 1671–1675, Bibcode : 1980ITED ... 27.1671L , doi : 10.1109 / T-ED.1980.20086 , S2CID  64469353 , Также в совместном выпуске, IEEE Journal of Solid-State Circuits 15 (4): 736–740, 1980.
  • Миллер, Джордж А. (1956), "Магическое число семь плюс или минус два" , Psychological Review , 63 (2): 81-97, DOI : 10,1037 / h0043158 , PMID  13310704.
  • Меринг, Рольф Х. (1990), "Проблемы с графами, связанные с компоновкой матрицы вентилей и сворачиванием PLA", в Tinhofer, G .; Mayr, E .; Noltemeier, H .; и другие. (ред.), Computational Graph Theory , Computing Supplementum, 7 , Springer-Verlag, pp. 17–51, ISBN 3-211-82177-5.
  • Monien, B .; Sudborough, IH (1988), "Min разрез NP-полный для краевых взвешенных дерев", Теоретическая информатика , 58 (1-3): 209-229, DOI : 10,1016 / 0304-3975 (88) 90028-X.
  • Оцуки, Тацуо; Мори, Хаджиму; Kuh, Ernest S .; Кашивабара, Тошинобу; Фудзисава, Тосио (1979), "Одномерный назначение логики ворота и графы интервалов", IEEE Transactions на схем и систем , 26 (9): 675-684, DOI : 10,1109 / TCS.1979.1084695.
  • Пэн, Шэн-Лунг; Хо, Чин-Вен; Сюй, Цань-шэн; Ко, Мин-Тат; Тан, Чуан И (1998), "Алгоритм линейного времени для построения оптимальной стратегии поиска узлов дерева", Proc. 4-й Int. Конф. Вычисления и комбинаторика (COCOON'98) , Lecture Notes in Computer Science, 1449 , Springer-Verlag, pp. 197–205.[ мертвая ссылка ] .
  • Проскуровский, Анджей; Телле, Ян Арне (1999), «Классы графов с моделями с ограниченным интервалом» (PDF) , Дискретная математика и теоретическая информатика , 3 : 167–176, заархивировано из оригинала (PDF) 06.06.2011 , извлечено в 2010 г. -05-06.
  • Робертсон, Нил ; Seymour, Павел (1983), "Graph несовершеннолетних I. За исключением леса.", Журнал комбинаторной теории, серии B , 35 (1): 39-61, DOI : 10,1016 / 0095-8956 (83) 90079-5.
  • Робертсон, Нил ; Seymour, Пол (2003), "Graph несовершеннолетний XVI исключающие непланарный граф..", Журнал комбинаторной теории, серии 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), "Линейный алгоритм определения ширины пути деревьев", в Bodendiek, R .; Хенн Р. (ред.), « Темы комбинаторики и теории графов» , Physica-Verlag, стр. 613–620..
  • Шеффлер, Петра (1992), «Оптимальное вложение дерева в интервальный граф за линейное время», Нешетржил, Ярослав ; Фидлер, Мирослав (ред.), Четвертый чехословацкий симпозиум по комбинаторике, графам и сложности , Elsevier.
  • Скодинис, Константин (2000), "Вычисление оптимальных линейных макетов деревьев за линейное время", Proc. 8-й Европейский симпозиум по алгоритмам (ESA 2000) , Lecture Notes in Computer Science, 1879 , Springer-Verlag, pp. 403–414, doi : 10.1007 / 3-540-45253-2_37 , ISBN 978-3-540-41004-1.
  • Скодинис, Константин (2003), «Построение линейных древовидных схем, оптимальных с точки зрения разделения вершин за линейное время», Журнал алгоритмов , 47 (1): 40–59, DOI : 10.1016 / S0196-6774 (02) 00225-0.
  • Сучан, Кароль; Тодинка, Иоан (2007), "Пропускная способность графов дуги окружности", Proc. Тридцать третий Международный семинар по теории графов концепций в области компьютерных наук (РГ 2007) , Lecture Notes в области компьютерных наук, 4769 , Springer-Verlag, стр 258-269,. Дои : 10.1007 / 978-3-540-74839-7_25.
  • Suderman, Мэтью (2004), "Pathwidth и многослойные рисунки деревьев" (PDF) , Международный журнал вычислительной геометрии и приложений , 14 (3): 203-225, DOI : 10,1142 / S0218195904001433 , архивируются от оригинала (PDF) на 2003-05-03.
  • Такахаши, Ацуши; Уэно, Шуичи; Кадзитаните, Йоджи (1994), "Минимальной ациклическую запрещенной несовершеннолетняя для семейства графов с ограниченной траекторией шириной", дискретная математика , 127 (1-3): 293-304, DOI : 10.1016 / 0012-365X (94) 90092- 2.