Перегляд вихідного коду сторінки Шляхова ширина графа

У [[Теорія графів|теорії графів]] '''шляхова декомпозиція''' графа ''G''&nbsp;— це, неформально, подання графа G у вигляді «потовщеного» [[Шлях (теорія графів)|шляху]]{{sfn|Diestel, Kühn|2005}}, а '''шляхова ширина''' графа ''G''&nbsp;— це число, що вимірює, наскільки граф G був потовщений. Формальніше, шляхова декомпозиція&nbsp;— це послідовності вершин підмножини графа G, такі, що кінцеві вершини кожного ребра з'являються в одній з підмножин і кожна вершина належить (хоча б) одній множині{{sfn|Robertson, Seymour|1983}}, а шляхова ширина на одиницю менша від розміру найбільшої множини в цій декомпозиції. Шляхова ширина відома також як '''інтервальна товщина''' (на одиницю менше від розміру [[Кліка (теорія графів)|найбільшої кліки]] інтервального [[Словник термінів теорії графів|суперграфа]] графа ''G''), '''величина вершинного розділення,''' чи '''вершинно-пошукове число'''{{sfn|Bodlaender|1998}}<ref>Багато використаних у статті терминів можна знайти у вступі до дисертації Ф.&nbsp;В.&nbsp;Фоміна ({{harv|Фомин|1996}})</ref>.

Шляхова ширина і шляхова декомпозиція є тісною аналогією з [[Деревна ширина (теорія графів)|деревною шириною]] і [[Деревна декомпозиція|деревною декомпозицією]]. Вони відіграють ключову роль у теорії [[Мінор графа|мінорів графа]]&nbsp;— сімейства графів, які замкнуті відносно мінорів графа і не включають усі [[Дерево (теорія графів)|дерева,]] можна схарактеризувати як такі, що мають обмежену шляхову ширину{{sfn|Robertson, Seymour|1983}}, і «вихори», що виникають у загальній структурній теорії сімейств графів, замкнутих за мінором, мають обмежену шляхову ширину{{sfn|Robertson, Seymour|2003}}. Шляхова ширина і графи з обмеженою шляховою шириною застосовуються в розробці [[Мікросхема|НВІС]], [[Візуалізація графів|візуалізації графів]] та [[Математична лінгвістика|комп'ютерній лінгвістиці]].

Задача знаходження шляхової ширини довільних графів є [[Клас складності NP|NP-складною]]. Більше того, NP-складною є навіть задача апроксимації шляхової ширини точно<ref name="npc"/>{{sfn|Bodlaender, Gilbert, Hafsteinsson, Kloks|1992}}. Однак ця задача є фіксовано-параметрично розв'язною&nbsp;— перевірку, чи має граф шляхову ширину ''k'', можна здійснити за час, який лінійно залежить від розміру графа, але суперекспоненціально від ''k.'' Крім того, для деяких особливих класів графів, таких як [[Дерево (теорія графів)|дерева]], шляхову ширину можна обчислити за поліноміальний час, не залежний від ''k''{{sfn|Bodlaender|1994}}<ref name="tree-algs"/>. Багато задач теорії графів можна ефективно розв'язати на графах з обмеженою шляховою шириною за допомогою [[Динамічне програмування|динамічного програмування]] на шляховій декомпозиції графа{{sfn|Arnborg|1985}}. Деревну декомпозицію можна також використовувати для оцінювання ємнісної складності алгоритмів динамічного програмування на графах з обмеженою деревною шириною{{sfn|Aspvall, Proskurowski, Telle|2000}}.

== Визначення ==
[[Файл:Pathwidth.JPG|міні|Приклад графа G з шляховою шириною 2 і його шляхова декомпозиція ширини 2. У нижній частині рисунка наведено той самий граф і шляхова декомпозиція з доданими кольорами для виразності. (Цей приклад узято з книги&nbsp;Бодлендера{{sfn|Bodlaender|1994|с =1–2}}, і додано кольори)]]
У першій відомій серії статей про [[Мінор графа|мінори графа]] Робертсон і Сеймур{{sfn|Robertson, Seymour|1983}} визначили шляхову декомпозицію графа ''G'' як послідовність підмножин ''X<sub>i</sub>'' вершин графа ''G'' з двома властивостями:
# Для кожного ребра ''G'' існує ''i'', таке, що обидві кінцеві точки ребра належать підмножині ''X<sub>i.</sub>''
# Для будь-яких трьох індексів ''i'' ≤ ''j'' ≤ ''k'', ''X<sub>i</sub>'' ∩ ''X<sub>k</sub>'' ⊆ ''X<sub>j</sub>''.
Друга з цих двох властивостей еквівалентна вимозі, що підмножини, які містять будь-яку вершину, утворюють неперервну підпослідовність усієї послідовності. Мовою пізнішої серії робіт Робертсона і Сеймура про мінори графа, шляхова декомпозиція&nbsp;— це деревна декомпозиція (''X'',''T''), в якій дерево ''T'' декомпозиції, що лежить нижче, є [[Шлях (теорія графів)|шляхом]].

Ширина шляхової декомпозиції визначається так само, як і для деревної декомпозиції, як max<sub>''i''</sub>&nbsp;|''X<sub>i</sub>''|&nbsp;−&nbsp;1, а шляхова ширина графа ''G'' дорівнює мінімальній ширині всіх шляхових декомпозицій графа ''G''. Віднімання одиниці від розміру ''X<sub>i</sub>'' в цьому визначенні мало впливає на більшість застосувань шляхової ширини, але зате робить шляхову ширину [[Шлях (теорія графів)|шляху]] рівною одиниці.

== Альтернативні описи ==
Як пише Бодлендер{{sfn|Bodlaender|1998}} шляхову ширину можна описати багатьма еквівалентними способами.

=== Склеювання послідовностей ===
[[Деревна декомпозиція|Деревну декомпозицію]] можна описати як послідовність графів ''G<sub>i</sub>'', які склеєні шляхом ототожнення пар вершин у сусідніх графах послідовності, і результатом цього склеювання є граф ''G''. Як графи ''G<sub>i</sub>'' можна взяти [[Породжений підграф|породжені підграфи]] множин ''X<sub>i</sub>'' у першому визначенні шляхової декомпозиції, зі склеюванням вершин у сусідніх породжених підграфах, якщо ці вершини породжені тією ж самою вершиною з ''G''. З іншого боку можна відновити ''X<sub>i</sub>'' як множини вершин графів ''G<sub>i</sub>''. Ширина деревної декомпозиції тоді на одиницю менша від максимального числа вершин в одному з графів ''G<sub>i</sub>''{{sfn|Robertson, Seymour|1983}}.

=== Інтервальна товщина ===
[[Файл:Interval_graph.svg|міні| Інтервальний граф з шляховою шириною два, на одиницю меншою від числа чотирьох максимальних клік ''ABC'', ''ACD'', ''CDE'' и ''CDF''.]]
Шляхова ширина будь-якого графа ''G'' на одиницю менша від найменшого [[Кліка (теорія графів)|клікового числа]] інтервального графа, що містить ''G'' як підграф{{sfn|Bodlaender|1998|с=13, Theorem 29}}. Тобто для будь-якої деревної декомпозиції графа ''G'' можна знайти інтервальний суперграф, і для будь-якого інтервального суперграфа ''G'' можна знайти деревну декомпозицію графа ''G'', ширина декомпозиції якої на одиницю менша від клікового числа інтервального графа.

З одного боку, припустимо, що деревна декомпозиція графа ''G'' задана. Тоді можна уявити вершини декомпозиції як точки на прямій (в тому порядку, в якому вони входять до шляху) і подати кожну вершину ''v'' як замкнутий інтервал, для якого ці точки є кінцевими. Наприклад, нехай (''X''<sub>1</sub>, …, ''X''<sub>r</sub>)&nbsp;— шляхова декомпозиція графа ''G'', точки на прямій&nbsp;— [1, …, r], тоді подання вершини ''v''&nbsp;— це інтервал <math>[min\{i|v  \in X_i\},max\{i|v  \in X_i\}]</math>. Тоді деревна декомпозиція вершин, що містять ''v'', відповідає кінцевим точкам інтервалу для ''v''. [[Граф перетинів]] інтервалів, утворений з вершин ''G,''&nbsp;— це інтервальний граф, що містить ''G'' як підграф. Його максимальні кліки задаються множиною інтервалів, що містять точки представлення, і їх розмір найбільшої кліки на одиницю більший від шляхової ширини графа ''G''.

З іншого боку, якщо ''G''&nbsp;— підграф інтервального графа з кліковим числом ''p''+1, то граф ''G'' має деревну декомпозицію ширини ''p'', вершини якої задані [[Кліка (теорія графів)|максимальними кліками]] інтервального графа. Наприклад, інтервальний граф, показаний з його інтервальним поданням на рисунку, має деревну декомпозицію з п'ятьма вершинами, відповідними п'ятьом максимальним клікам ''ABC'', ''ACD'', ''CDE'', ''CDF та'' ''FG''. Розмір максимальної кліки дорівнює трьом, а ширина цієї деревної декомпозиції дорівнює двом.

Ця еквівалентність між шляховою шириною й інтервальною товщиною є тісною аналогією з еквівалентністю між деревною шириною і мінімальним кліковим числом (мінус одиниця) хордального графа, для якого даний граф є підграфом. Інтервальні графи є особливим випадком хордальних графів, а хордальні графи можна подати у вигляді графів перетинів піддерев спільних дерев, що узагальнює підхід, за якого інтервальні графи інтерпретуються як графи перетинів підшляхів шляху.

=== Величина вершинного поділу ===
Припустимо, що вершини графа ''G'' [[Лінійно впорядкована множина|лінійно впорядковані]]. Тоді величина вершинного поділу графа ''G''&nbsp;— це найменше число ''s'', таке, що для кожної вершини ''v'' максимум ''s'' вершин передують ''v'' в упорядкуванні, які мають ''v'' або одну з наступних за нею вершин в околі. Величина вершинного поділу графа ''G''&nbsp;— це мінімальна величина вершинного поділу будь-якого лінійного впорядкування графа ''G''. Величину вершинного поділу ввели Елліс, Садбороу та Тернер{{sfn|Ellis, Sudborough, Turner|1983}}, і вона дорівнює шляховій ширині графа ''G''{{sfn|Kinnersley|1992}}{{sfn|Bodlaender|1998|с=Theorem 51}}. Це випливає з раніше згаданої еквівалентності інтервальних графів і клікових чисел&nbsp;— якщо ''G'' є підграфом інтервального графа ''I'', поданого (як на рисунку) так, що всі кінці інтервалів різні, то порядок лівих кінців інтервалів графа ''I'' мають величину вершинного поділу на одиницю меншу за клікове число графа ''I''. З іншого боку, з лінійного впорядкування графа ''G'' можна отримати інтервальне подання, в якому ліва кінцева точка інтервалу для вершини ''v'' є позицією в упорядкуванні, а права кінцева точка є позицією сусіда ''v'', який в упорядкуванні останній.

=== Вершинно-пошукове число ===
Гра «пошук вершини» на графі&nbsp;— це вид гри [[переслідування-ухилення]], в якій множина переслідувачів спільно намагаються вистежити втікача, який сховався в графі. Переслідувачі розміщуються у вершинах графа, тоді як утікач може перебувати на будь-якому ребрі графа, його місце розташування і ходи переслідувачам не помітні. Під час чергового ходу деякі (або всі) переслідувачі можуть перейти (довільним чином, не обов'язково уздовж ребер) з однієї вершини в іншу, а втікач рухається потім уздовж будь-якого шляху на графі, але не може проходити через зайняті переслідувачами вершини. Втікач спійманий, коли обидва кінці дуги, на якій він перебуває, зайняті переслідувачами. Вершинно-пошукове число графа&nbsp;— це найменше число переслідувачів, необхідних для гарантованого впіймання втікача незалежно від його поведінки. Як показали Кіроузіс і [[Христос Пападімітріу|Пападімітріу]]{{sfn|Kirousis, Papadimitriou|1985}}, вершинно-пошукове число графа дорівнює його інтервальній товщині. Оптимальною стратегією для переслідувачів є ходи, в яких переслідувачі послідовно утворюють розділювальні множини лінійного впорядкування з мінімальною величиною вершинного поділу.

== Межі ==
[[Файл:Caterpillar_tree.svg|міні|[[Граф-гусениця]], максимальний граф з шляховою шириною один.]]
Будь-який граф з ''n'' вершинами і шляховою шириною ''k'' має максимум ''k''(''n'' − ''k'' + (''k'' − 1)/2)) ребер, і [[Максимальні та мінімальні елементи|максимальні]] графи з шляховою шириною ''k'' (графи, до яких не можна додати ребро без збільшення шляхової ширини) мають точно таке число ребер. Максимальний граф з шляховою шириною ''k'' повинен бути або ''k''-шляхом, або ''k''-гусеницею, тобто одного з двох особливих видів ''k''-дерева. ''k''-дерево&nbsp;— це&nbsp;[[хордальный граф]]&nbsp;з точно ''n'' − ''k'' [[Кліка (теорія графів)|максимальними кліками]], кожна з яких містить ''k'' + 1 вершину. В ''k''-дереві, яке саме не є (''k'' + 1)-клікою, кожна максимальна кліка або ділить граф на дві або більше компоненти, або містить одиничну листову вершину, вершину, яка належить тільки одній максимальній кліці. ''k''-шлях&nbsp;— це ''k''-дерево з максимум двома листками, а ''k''-гусениця&nbsp;— це ''k''-дерево, яке можна поділити на ''k''-шлях і множину ''k''-листків, кожен з яких суміжний з [[Вершинний сепаратор (теорія графів)|сепаратором]] ''k''-кліки ''k''-шляху. Зокрема, максимальні графи шляхової ширини одиниця&nbsp;— це точно [[графи-гусениці]]{{sfn|Proskurowski, Telle|1999}}.

Оскільки шляхові декомпозиції є особливими випадками деревних декомпозицій, шляхова ширина будь-якого графа більша або дорівнює його [[Деревна ширина (теорія графів)|деревній ширині]]. Шляхова ширина також менша або дорівнює ширині розрізу, мінімального числа ребер, які перетинають будь-який перетин між вершинами з меншим індексом і великим індексом в оптимальному лінійному впорядкуванні вершин графа. Це випливає з факту, що величина вершинного поділу, число вершин з меншим індексом з сусідами, що мають більший індекс, не більша від числа розрізаючих ребер{{sfn|Korach, Solel|1993|с=99, Lemma 3}}{{sfn|Bodlaender|1998|с=24, Theorem 47}}. З цієї ж причини ширина розрізу не перевищує шляхової ширини, помноженої на [[Степінь вершини (теорія графів)|максимальний степінь]] вершин у даному графі{{sfn|Korach, Solel|1993|с=99, Lemma 1}}{{sfn|Bodlaender|1998|с=24, Theorem 49}}.

Будь-який [[Дерево (теорія графів)|ліс]] з ''n'' вершинами має шляхову ширину O(log&nbsp;''n''){{sfn|Korach, Solel|1993|с=99, Theorem 5}}{{sfn|Bodlaender|1998|с=30, Theorem 66}}<ref> Шеффлер ({{harvtxt|Scheffler|1992}}) дає сильнішу межу log<sub>3</sub>(2''n''&nbsp;+&nbsp;1) шляхової ширини лісу з ''n'' вершинами.</ref>. Для лісу можна завжди знайти стале число вершин, видалення яких приводить до лісу, який можна розбити на два менших ліси з максимум 2''n''/3 вершин у кожному з цих лісів. Лінійне впорядкування, утворене рекурсивним застосуванням такого розбиття, має логарифмічне пошукове число для вершин. Та сама техніка, застосована до деревної декомпозиції графа, показує, що якщо деревна ширина графа ''G'' з ''n'' вершинами дорівнює ''t'', то шляхова ширина графа ''G'' дорівнює O(''t''&nbsp;log&nbsp;''n''){{sfn|Korach, Solel|1993|с=100, Theorem 6}}{{sfn|Bodlaender|1998|с=10, Corollary 24}}. Оскільки [[Зовніпланарний граф|зовніпланарні графи]], [[Паралельно-послідовний граф|паралельно-послідовні графи]] та [[Граф Халіна|графи Халіна]] всі мають обмежену деревну ширину, всі вони мають максимум логарифмічну шляхову ширину.

Крім того, що шляхова ширина пов'язана з деревною шириною, вона пов'язана з [[Клікова ширина|кліковою шириною]] і шириною розрізу через [[Реберний граф|реберні графи]]. Реберний граф ''L''(''G'') графа ''G'' має вершину для кожного ребра графа ''G'' і дві вершини в ''L''(''G'') суміжні, якщо відповідні два ребра ''G'' мають спільні кінцеві точки. Будь-яке сімейство графів має обмежену шляхову ширину [[тоді й лише тоді]], коли його реберні графи мають обмежену лінійну клікову ширину, де лінійна клікова ширина замінює операцію об'єднання у визначенні клікової ширини на операцію приєднання окремої нової вершини{{sfn|Gurski, Wanke|2007}}. Якщо [[зв'язний граф]] з трьома або більше вершинами має максимальний степінь 3, його ширина розрізу дорівнює величині вершинного поділу його реберного графа{{sfn|Golovach|1993}}.

В будь-якому [[Планарний граф|планарному графі]] шляхова ширина в гіршому випадку пропорційна квадратному кореню від кількості вершин{{sfn|Bodlaender|1998|с=10, Corollary 23}}. Один зі способів пошуку шляхової декомпозиції з такою шириною&nbsp;— (подібно до шляхової декомпозиції з логарифмічною деревною шириною, описаної вище) використовувати [[Теорема про планарне розбиття|теорему про планарне розбиття]], щоб знайти множини з O(√''n'') вершин, видалення яких розбиває граф на два підграфи з максимум 2''n''/3 вершинами в кожному, і з'єднати рекурсивно побудовані для цих двох підграфів шляхові декомпозиції. Цю ж техніку можна застосувати до будь-якого класу графів, для яких виконується подібна теорема про розбиття{{sfn|Bodlaender|1998|с=9, Theorem 20}}. Оскільки будь-яке сімейство графів, замкнуте щодо взяття мінорів, як і в разі планарних графів, має розбивальну множину вершин розміру O(√''n''){{sfn|Alon, Seymour, Thomas|1990}}, звідси випливає, що шляхова ширина графів у будь-якому фіксованому замкнутому відносно мінорів сімействі знову дорівнює O(√''n''). Для деяких класів планарних графів шляхова ширина графа і шляхова ширина його [[Двоїстий граф|двоїстого графа]] повинні лежати в інтервалі, межі якого лінійно залежать від значень&nbsp;— такі межі відомі для двозв'язних зовнішніх планарних графів{{sfn|Bodlaender, Fomin|2002}}{{sfn|Coudert, Huc, Sereni|2007}} і для графів багатогранників{{sfn|Fomin, Thilikos|2007}}{{sfn|Amini, Huc, Pérennes|2009}}. Для двозв'язних планарних графів шляхова ширина двоїстого графа менша, ніж шляхова ширина реберного графа{{sfn|Fomin|2003}}. Залишається відкритим питання, чи буде шляхова ширина планарного графа і його двоїстого завжди в лінійних межах для інших випадків.

Для деяких класів графів доведено, що шляхова ширина графа  і деревна ширина завжди рівні між собою&nbsp;— це виконується для [[Кограф|кографів]]{{sfn|Bodlaender, Möhring|1990}}, [[Граф перестановки|графів перестановки]]{{sfn|Bodlaender, Kloks, Kratsch|1993}}, [[Доповнення графа|доповнень графів]] порівнянності і [[Граф порівнянності|графів порівнянності]]{{sfn|Habib, Möhring|1994}} [[Інтервальний порядок|інтервальних порядків]]{{sfn|Garbe|1995}}.

{{unsolved|математики|Яка максимальна шляхова ширина [[Кубічний граф|кубічного графа]] з <math>n</math> вершинами?}}
В будь-якому [[Кубічний граф|кубічному графі]] або, більш загально, будь-якому графі з максимальним степенем вершин 3, шляхова ширина не перевищує ''n''/6&nbsp;+&nbsp;o(''n''), де ''n''&nbsp;— кількість вершин графа. Існують кубічні графи зі шляховою шириною 0,082''n'', але невідомо, як скоротити цей розрив між [[Верхня та нижня межа|нижньою межею]] і верхньою межею ''n''/6{{sfn|Fomin, Høie|2006}}.

== Обчислення шляхових декомпозицій ==
Визначення, чи не перевищує шляхова ширина заданого значення ''k'' для заданого графа, є [[NP-повна задача|NP-повною]] задачею, якщо ''k'' є вхідним параметром<ref name="npc">{{harvnb|Kashiwabara, Fujisawa|1979}}; {{harvnb|Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa|1979}}; {{harvnb|Lengauer|1981}}; {{harvnb|Arnborg, Corneil, Proskurowski|1987}}.</ref>. Найвідоміші часові межі обчислення шляхової ширини довільного графа з ''n'' вершинами мають вигляд O(2<sup>''n''</sup>&nbsp;''n''<sup>''c''</sup>) за деякої константи ''c''{{sfn|Fomin, Kratsch, Todinca, Villanger|2008}}. Проте відомі деякі алгоритми обчислення шляхової декомпозиції з більшою ефективністю, якщо шляхова ширина мала, якщо клас вхідних графів обмежений, або потрібно обчислити шляхову ширину приблизно.

=== Фіксовано-параметрично розв'язність ===
Шляхова ширина {{нп|Фіксовано-параметрично розв'язність|фіксовано-параметрично розв'язна|en|fixed-parameter tractable}}&nbsp;— для будь-якого сталого ''k'' можна перевірити, чи не перевершує шляхова ширина величини ''k'', і, якщо не перевершує, знайти шляхову декомпозицію ширини ''k'' за лінійний час. У цілому, ці алгоритми працюють у два етапи. На першому етапі використовується припущення, що граф має шляхову ширину ''k'', для пошуку шляхової декомпозиції або деревної декомпозиції. Ця декомпозиція не оптимальна, але її ширина може бути обмежена функцією від ''k''. На другому етапі застосовується алгоритм [[Динамічне програмування|динамічного програмування]] для пошуку оптимальної декомпозиції. Однак часові межі для відомих алгоритмів цього типу експоненціальні від ''k''<sup>2</sup> і не становлять практичного інтересу, хіба що для малих значень ''k''{{sfn|Downey, Fellows|1999|с=12}}. Для випадку ''k''&nbsp;=&nbsp;2 Фляйтер дав алгоритм з лінійним часом роботи, заснований на структурній декомпозиції графів зі шляховою шириною 2{{sfn|de Fluiter|1997}}.

=== Особливі класи графів ===
Бодлендер {{sfn|Bodlaender|1994}} дав огляд складності задач обчислення шляхової ширини на різних особливих класах графів. Визначення, чи перевищує шляхова ширина графа ''G'' величину ''k'', залишається NP-повною задачею, якщо ''G'' береться із графів обмеженого степеня{{sfn|Monien, Sudborough|1988}}, [[Планарний граф|планарних графів]]{{sfn|Monien, Sudborough|1988}}, планарних графів обмеженого степеня{{sfn|Monien, Sudborough|1988}}, хордальних графів{{sfn|Gusted|1993}}, хордальних доміно<ref>{{harvnb|Kloks, Kratsch, Müller|1995}}. Хордальне доміно&nbsp;— це хордальний граф, у якому будь-яка вершина належить максимум двом максимальним клікам</ref>, [[Доповнення графа|доповнень]] графів порівнянності{{sfn|Habib, Möhring|1994}}, і двочасткових [[Дистанційно-успадковуваний граф|дистанційно-успадковуваних графів]]{{sfn|Kloks, Bodlaender, Müller, Kratsch|1993}}. Звідси негайно випливає, що задача також NP-повна для сімейств графів, що містять двочасткові дистанційно-успадковувані графи, включно з двочастковими графами, хордальними двочастковими графами, дистанційно-успадковуваними графами та [[Коловий граф|коловими графами]]{{sfn|Kloks, Bodlaender, Müller, Kratsch|1993}}.

Однак шляхову ширину можна обчислити за лінійний час для дерев і лісів<ref name="tree-algs">{{harvnb|Möhring|1990}}; {{harvnb|Scheffler|1990}}; {{harvnb|Ellis, Sudborough, Turner|1994}}; {{harvnb|Coudert, Huc, Mazauric|1998}}; {{harvnb|Peng, Ho, Hsu, Ko, Tang|1998}}; {{harvnb|Skodinis|2000}}; {{harvtxt|Skodinis|2003}}.</ref>. Можна обчислити цю величину за поліноміальний час для графів обмеженої деревної ширини, до яких належать паралельно-послідовні графи, зовніпланарні графи і графи Халіна<ref name="bounded-tw-algs">{{harvtxt|Bodlaender|1996}}; {{harvtxt|Bodlaender, Kloks|1996}}</ref>, а також [[Розщеплюваний граф|розщеплювані графи]]{{sfn|Kloks, Bodlaender|1992}}{{sfn|Gusted|1993}}, доповнення хордальних графів<ref>Гарбе ({{harvtxt|Garbe|1995}}) приписує цей результат тезам дисертації Тона Клокса 1993 року. Алгоритм поліноміального часу Гарбе для графів порівнянності інтервальных упорядкувань узагальнює цей результат, оскільки будь-який хордальний граф має бути графом порівнянності такого типу.</ref>, графи перестановок{{sfn|Bodlaender, Kloks, Kratsch|1993}}, кографи{{sfn|Bodlaender, Möhring|1990}}, [[Граф дуг кола|графи дуг кола]]{{sfn|Suchan, Todinca|2007}}, графи порівнянності інтервальних порядків{{sfn|Garbe|1995}} і, звичайно, самі інтервальні графи, оскільки для них шляхова ширина просто на одиницю менша від максимального числа інтервального покриття будь-якої точки в інтервальному поданні графа.

=== Апроксимаційні алгоритми ===
{{Докладніше|Апроксимаційний алгоритм}}
NP-складною задачею є апроксимація шляхової ширини графа адитивною константою{{sfn|Bodlaender, Gilbert, Hafsteinsson, Kloks|1992}}. Найкращий відомий апроксимаційний коефіцієнт апроксимаційних алгоритмів поліноміального часу для шляхової ширини дорівнює O((log&nbsp;''n'')<sup>3/2</sup>){{sfn|Feige, Hajiaghayi, Lee|2005}}. Ранні апроксимаційні алгоритми для шляхової ширини можна знайти у Бодлендера, Гілберта, Хафштейнссона, Клокса{{sfn|Bodlaender, Gilbert, Hafsteinsson, Kloks|1992}} і Гуха{{sfn|Guha|2000}}. Для апроксимації обмежених класів графів див. книгу Клокса і Бодлендера{{sfn|Kloks, Bodlaender|1992}}.

== Мінори графа ==
[[Мінор графа]] ''G''&nbsp;— це інший граф, створений з G [[Стягування ребра|стягуванням ребер]], видаленням ребер і вершин. Мінор графа має глибоку теорію, в якій деякі важливі результати використовують шляхову ширину.

=== Виключення лісу ===
Якщо сімейство ''F'' графів замкнуте відносно операції взяття мінорів (будь-який мінор члена сімейства ''F'' також міститься в ''F''), тоді за [[Теорема Робертсона — Сеймура|теоремою Робертсона&nbsp;— Сеймура]] сімейство ''F'' можна схарактеризувати як графи, що не містять мінорів з ''X'', де ''X''&nbsp;— скінченна множина [[Характеризація забороненими графами|заборонених мінорів]]{{sfn|Robertson, Seymour|2004}}. Наприклад, [[теорема Вагнера]] стверджує, що планарні графи&nbsp;— це графи, які не містять ні повного графа ''K''<sub>5</sub>, ні повного двочасткового графа ''K''<sub>3,3</sub> як мінорів. У багатьох випадках властивості ''F'' і властивості ''X'' тісно пов'язані, і перший результат такого типу отримали Робертсон і Сеймур{{sfn|Robertson, Seymour|1983}} і він пов'язує існування обмеженої шляхової ширини з наявністю лісу в сім'ї заборонених мінорів. Детальніше, визначимо сімейство ''F'' графів як таке, що має ''обмежену шляхову ширину'', якщо існує константа ''p'', така, що будь-який граф з ''F'' має шляхову ширину, яка не перевищує ''p''. Тоді мінорно-замкнуте сімейство ''F'' має обмежену шляхову ширину [[тоді й лише тоді]], коли множина ''X'' заборонених мінорів для ''F'' включає хоча б один ліс.

З одного боку, цей результат можна довести прямо&nbsp;— а саме, що якщо ''X'' не містить хоча б одного лісу, то вільні від ''X''-мінорів графи не мають обмеженої шляхової ширини. В цьому випадку вільні від ''X''-мінорів графи включають усі ліси, і зокрема [[Досконале бінарне дерево|досконалі бінарні дерева]]. Але досконалі бінарні дерева з 2''k''&nbsp;+&nbsp;1 рівнями мають шляхову ширину ''k'', так що в цьому випадку вільні від ''X''-мінорів графи мають необмежену шляхову ширину. З іншого боку, якщо ''X'' містить ліс з ''n'' вершинами, то вільні від ''X''-мінорів графи мають шляхову ширину, яка не перевищує ''n''&nbsp;−&nbsp;2{{sfn|Bienstock, Robertson, Seymour, Thomas|1991}}{{sfn|Diestel|1995}}{{sfn|Cattell, Dinneen, Fellows|1996}}.

=== Оцінки шляхової ширини ===
[[Файл:Pathwidth-1_obstructions.svg|міні|[[Характеризація забороненими графами|Заборонені мінори]] для графів з шляховою шириною 1.]]
Властивість мати шляхову ширину не більше ніж ''p'' є, сама по собі, замкнутою за взяттям мінорів властивістю&nbsp;— якщо ''G'' має шляхову декомпозицію з шириною, що не перевищує ''p'', то та ж сама шляхова декомпозиція залишається правильною, якщо видалити будь-яке ребро з ''G'', а також будь-яку вершину можна видалити з графа ''G''  і його шляхової декомпозиції без збільшення ширини. Стягування ребра також можна завершити без збільшення ширини декомпозиції злиттям підшляхів, що являють собою два кінці стягуваного ребра. Таким чином, графи зі шляховою шириною, що не перевищує ''p'', можна схарактеризувати множиною ''X<sub>p</sub>'' заборонених мінорів{{sfn|Robertson, Seymour|2004}}{{sfn|Kinnersley|1992}}{{sfn|Takahashi, Ueno, Kajitani|1994}}{{sfn|Bodlaender|1998|с=8}}.

Хоча ''X<sub>p</sub>'' обов'язково включає щонайменше один ліс, невірно, що всі графи в ''X<sub>p</sub>'' є лісами. Наприклад, ''X''<sub>1</sub> складається з двох графів, дерева з сімома вершинами і трикутника ''K''<sub>3</sub>. Однак множину дерев у ''X<sub>p</sub>'' можна точно описати&nbsp;— це точно ті дерева, які можна утворити з трьох дерев із ''X''<sub>''p''&nbsp;−&nbsp;1</sub> утворенням нового кореня і з'єднанням його ребрами з довільно вибраними вершинами менших дерев. Наприклад, дерево із сімома вершинами в ''X''<sub>1</sub> утворене з дерев з двома вершинами (одне ребро) з ''X''<sub>0</sub>. Ґрунтуючись на цій побудові, можна показати, що число заборонених мінорів у ''X''<sub>''p''</sub> не менше від (''p''!)<sup>2</sup>{{sfn|Kinnersley|1992}}{{sfn|Takahashi, Ueno, Kajitani|1994}}{{sfn|Bodlaender|1998|с=8}}. Повну множину ''X''<sub>2</sub> заборонених мінорів для графів зі шляховою шириною 2 обчислено. Ця множина містить 110 різних графів{{sfn|Kinnersley, Langston|1994}}.

=== Структурна теорія ===
[[Структурна теорема графів]] сімейств замкнутих за мінорами графів стверджує, що для будь-якого такого сімейства ''F'', його графи можна розкласти на [[Сума за клікою|суму за клікою]] графів, які можна вкласти в поверхні обмеженого [[Рід (математика)|роду]] разом з обмеженим числом [[Верхівковий граф|верхівок]] і вихорів для кожної компоненти суми за клікою. Верхівка&nbsp;— це вершина, яка суміжна з усіма вершинами компоненти, а вихор&nbsp;— це граф обмеженої шляхової ширини, що приклеюється до грані компоненти з укладенням обмеженого роду. Циклічний порядок вершин навколо грані, в яку вихор укладено, повинен бути сумісний з деревною декомпозицією вихору в тому сенсі, що розрив циклу для утворення лінійного впорядкування повинен привести до впорядкування з обмеженою величиною вершинного поділу{{sfn|Robertson, Seymour|2003}}. Ця теорія, в якій шляхова ширина тісно пов'язана з довільними сімействами графів, замкнутих щодо мінорів, має важливе алгоритмічне застосування{{sfn|Demaine, Hajiaghayi, Kawarabayashi|2005}}.

== Застосування ==

=== НВІС ===
Під час розробки [[Мікросхема|НВІС]] задача розділення вершин спочатку вивчалася як шлях поділу ланцюгів на менші підсистеми з малим числом компонент на межі між системами{{Sfn|Monien, Sudborough|1988}}.

Отцукі, Морі, Кух і Кашівабара{{Sfn|Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa|1979}} використовували інтервальну товщину для моделювання числа провідників, необхідних в одновимірному розташуванні ланцюгів НВІС, утворених множиною модулів, які необхідно з'єднати системою мереж. У їхній моделі можна утворити граф, у якому вершини представляють ланцюги і в якому дві вершини з'єднано ребром, якщо їхні ланцюги приєднано до одного у того ж модуля. Тобто якщо модулі й ланцюги розуміються як вершини і гіперребра [[Гіперграф|гіперграфа]], то граф, утворений з них, є [[Реберний граф гіперграфа|реберним графом гіперграфа]]. Інтервальне подання суперграфа цього реберного графа разом з [[Розфарбовування графів|розфарбуванням]] суперграфа описує розташування ланцюгів уздовж горизонтальних доріжок (одна доріжка на кожен колір), так що модулі можна розташувати вздовж доріжок у лінійному порядку і з'єднати з потрібними ланцюгами. З факту, що інтервальні графи є [[Досконалий граф|досконалими]]{{Sfn|Berge|1967}}, випливає, що число кольорів, необхідних для оптимальної розкладки такого типу, дорівнює кліковому числу інтервального доповнення графа ланцюгів.

Матрична укладання перемикачів{{Sfn|Lopez, Law|1980}} є специфічним видом [[КМОН]] НВІС укладання для ланцюгів [[Алгебра логіки|алгебри логіки]]. В матричних укладаннях перемикачів сигнал поширюється вздовж «ліній» (вертикальних відрізків), тоді як кожен перемикач утворюється послідовністю елементів, розташованих на горизонтальному відрізку. Таким чином, горизонтальні відрізки для кожного перемикача повинні перетинати вертикальні відрізки для кожної лінії, яка служить входом або виходом перемикача. Як і в укладаннях Отцукі, Морі, Куха і Кашівабара{{Sfn|Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa|1979}} укладання такого типу, що мінімізує число вертикальних прямих, можна знайти, обчисливши шляхову ширину графа, що має прямі як вершини, а пари прямих, що належать перемикачу, як ребра{{Sfn|Fellows, Langston|1989}}. Той самий алгоритмічний підхід можна також використати для моделювання задач укладання в [[ПЛІС|програмованих логічних інтегральних схемах]]{{Sfn|Möhring|1990}}{{Sfn|Ferreira, Song|1992}}.

=== Візуалізація графів ===
Шляхова ширина має кілька застосувань для [[Візуалізація графів|візуалізації графів]]:

* Мінімальні графи, що мають задане [[число схрещень]], мають шляхову ширину, обмежену функцією від числа схрещень{{Sfn|Hliněny|2003}}.
* Число паралельних прямих, на яких можна розташувати вершини дерева без перетину ребер (за різних природних обмежень на способи, якими суміжні вершини можна помістити на прямих з урахуванням послідовності прямих) пропорційне шляховій ширині дерева{{Sfn|Suderman|2004}}.
* ''k''-перетинний ''h''-рівневий малюнок графа ''G''&nbsp;— це розташування вершин графа ''G'' на ''h'' різних горизонтальних прямих з ребрами у вигляді монотонних (представлених ламаними) шляхів між прямими, в якому є не більше ніж ''k'' схрещень. Графи з таким поданням мають шляхову ширину, обмежену функцією від ''h'' і ''k''. Таким чином, якщо величини ''h'' і ''k'' сталі, можна за лінійний час визначити, чи має граф ''k''-перетинний ''h''-рівневий малюнок{{Sfn|Dujmović, Fellows, Kitching и др.|2008}}.
* Граф з ''n'' вершинами і шляховою шириною ''p'' можна вкласти в тривимірну ґратку розміру {{Nobr|''p'' × ''p'' × ''n''}} таким чином, що ніякі два ребра (представлені прямолінійними відрізками між точками ґратки) не перетинаються. Таким чином, графи обмеженої шляхової ширини мають вкладення цього типу з лінійним об'ємом{{Sfn|Dujmović, Morin, Wood|2003}}.

=== Проєктування компіляторів ===
Під час [[Компілятор|трансляції]] [[Мова програмування високого рівня|високорівневих мов програмування]] шляхова ширина виникає в задачі переупорядкування лінійного коду (тобто без коду [[Потік керування|керувальної логіки]]&nbsp;— переходів і циклів) таким чином, що всі значення, обчислені в коді, можуть бути поміщені [[Розподіл регістрів|в машинні регістри]], а не витіснені в основну пам'ять. У цьому застосуванні відтрансльований код подається у вигляді [[Спрямований ациклічний граф|спрямованого ациклічного графа]] (САГ), у якому вершини представляють вхідні значення коду і значення, обчислені внаслідок операцій усередині коду. Ребро з вершини ''x'' у вершину ''y'' в цьому САГ представляє факт, що значення ''x'' є одним зі вхідних параметрів для операції ''y''. [[Топологічне сортування]] вершин у цьому САГ представляє правильне сортування коду, а число регістрів, потрібних для виконання коду в цьому порядку задається величиною вершинного розділення впорядкування{{Sfn|Bodlaender, Gustedt, Telle|1998}}.

Для будь-якого фіксованого числа ''w'' регістрів у машині можна визначити за лінійний час, чи можна фрагмент лінійного коду переупорядкувати так, що для коду буде потрібно максимум ''w'' регістрів. Якщо величина вершинного топологічного розділення впорядкування не перевершує ''w'', мінімальне вершинне розділення серед усіх впорядкувань не може бути більшим, так що неорієнтовані графи, утворені нехтууванням орієнтації САГ, описаного вище, повинні мати шляхову ширину, що не перевершує ''w''. Можна перевірити, чи правильно це за допомогою відомих фіксовано-параметрично розв'язних алгоритмів для шляхової ширини, і, якщо правильно, знайти шляхову декомпозицію для неорієнтованих графів за лінійний час у припущенні, що ''w'' є константою. Як тільки деревну декомпозицію знайдено, топологічне сортування з шириною ''w'' (якщо таке існує) можна знайти з використанням динамічного програмування, знову ж таки за лінійний час{{Sfn|Bodlaender, Gustedt, Telle|1998}}.

=== Лінгвістика ===
Карнаї і Туца{{Sfn|Kornai, Tuza|1992}} описали застосування шляхової ширини для [[Обробка природної мови|обробки природної мови]]. В цьому застосуванні речення моделюються у вигляді графів, у яких вершини представляють слова, а ребра представляють зв'язки між словами. Наприклад, якщо прикметник модифікує іменник, то граф має ребро між цими двома словами. Через обмежений обсяг короткочасної людської пам'яті Міллер{{Sfn|Miller|1956}}, Корнаї і Туца стверджують, що цей граф повинен мати обмежену шляхову ширину (конкретніше, вони стверджують, що ця шляхова ширина не перевищує шести), в іншому випадку люди не могли б розпізнавати мову правильно.

=== Експоненційні алгоритми ===
Багато задачі теорії графів можна ефективно розв'язати на графах з малою шляховою шириною за допомогою [[Динамічне програмування|динамічного програмування]], спираючись на шляхову декомпозицію графа{{Sfn|Arnborg|1985}}. Наприклад, якщо лінійне упорядкування вершин графа ''G'' з ''n'' вершинами задано і величина вершинного розділення дорівнює ''w'', то можна знайти найбільшу незалежну множину графа ''G'' за час {{Nobr|O(2<sup>''w''</sup> ''n'')}}{{Sfn|Fomin, Høie|2006}}. На графі з обмеженою шляховою шириною цей підхід веде до фіксовано-параметрично розв'язних алгоритмів, параметризованих за шляховою шириною{{Sfn|Fellows, Langston|1989}}. Такі результати не часто зустрічаються в літературі, оскільки вони належать до групи схожих алгоритмів, параметризованих за деревною шириною. Однак шляхова ширина з'являється навіть в алгоритмах динамічного програмування, заснованих на деревній ширині, при вимірюванні [[Просторова складність алгоритму|просторової складності]] цих алгоритмів{{Sfn|Aspvall, Proskurowski, Telle|2000}}.

Той самий метод динамічного програмування можна застосувати до графів з необмеженою шляховою шириною, що приводить до алгоритмів, які розв'язують непараметризовані задачі на графах за [[Часова складність алгоритму|експоненційний час]]. Наприклад, комбінація підходу динамічного програмування з фактом, що кубічні графи мають шляхову ширину ''n''/6&nbsp;+&nbsp;o(''n''), показує, що для кубічних графів максимальну незалежну множину можна побудувати за час O(2<sup>''n''/6&nbsp;+&nbsp;o(''n'')</sup>), що швидше від відомих до цього методів{{Sfn|Fomin, Høie|2006}}. Схожий підхід веде до поліпшених алгоритмів експоненційного часу для задач [[Максимальний розріз графа|максимального розрізу]] і [[Домінівна множина|мінімальної домінівної множини]] для кубічних графів{{Sfn|Fomin, Høie|2006}} і для деяких інших NP-складних оптимізаційних задач{{Sfn|Kneis, Mölle, Richter, Rossmanith|2005}}{{Sfn|Björklund, Husfeldt|2008}}.

== Див. також ==
* [[Інтервальна розмірність графа]], інший шлях вимірювання складності довільних графів у термінах інтервальних графів
* [[Деревна глибина (теорія графів)|Деревна глибина]]&nbsp;— число, яке обмежене для мінорно-замкнутих сімейств графів тоді й лише тоді, коли сімейство не містить шляху
* [[Виродження (теорія графів)|Виродження]], міра розрідженості графа, що не більша від шляхової ширини графа
* {{нп|Стрічкова ширина графа||en|Graph bandwidth}}, інша NP-повна задача оптимізації, яка використовує лінійні укладення графів
* [[Число Стралера]], міра щільності кореневих дерев, що визначається подібно до шляхової ширини неорієнтованих дерев
* [[Деревна ширина (теорія графів)|Деревна ширина]]
* [[Клікова ширина]]
,

== Примітки ==
{{примітки|2}}

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

[[Категорія:Теорія мінорів графів]]
[[Категорія:Інваріанти графа]]
[[Категорія:NP-повні задачі]]