У теорії графів шляхова декомпозиція графа G — це, неформально, подання графа G у вигляді «потовщеного» шляху, а шляхова ширина графа G — це число, що вимірює, наскільки граф G був потовщений. Формальніше, шляхова декомпозиція — це послідовності вершин підмножини графа G, такі, що кінцеві вершини кожного ребра з'являються в одній з підмножин і кожна вершина належить (хоча б) одній множині, а шляхова ширина на одиницю менша від розміру найбільшої множини в цій декомпозиції. Шляхова ширина відома також як інтервальна товщина (на одиницю менше від розміру найбільшої кліки інтервального суперграфа графа G), величина вершинного розділення, чи вершинно-пошукове число.
Шляхова ширина і шляхова декомпозиція є тісною аналогією з деревною шириною і деревною декомпозицією. Вони відіграють ключову роль у теорії мінорів графа — сімейства графів, які замкнуті відносно мінорів графа і не включають усі дерева, можна схарактеризувати як такі, що мають обмежену шляхову ширину, і «вихори», що виникають у загальній структурній теорії сімейств графів, замкнутих за мінором, мають обмежену шляхову ширину. Шляхова ширина і графи з обмеженою шляховою шириною застосовуються в розробці НВІС, візуалізації графів та комп'ютерній лінгвістиці.
Задача знаходження шляхової ширини довільних графів є NP-складною. Більше того, NP-складною є навіть задача апроксимації шляхової ширини точно. Однак ця задача є фіксовано-параметрично розв'язною — перевірку, чи має граф шляхову ширину k, можна здійснити за час, який лінійно залежить від розміру графа, але суперекспоненціально від k. Крім того, для деяких особливих класів графів, таких як дерева, шляхову ширину можна обчислити за поліноміальний час, не залежний від k. Багато задач теорії графів можна ефективно розв'язати на графах з обмеженою шляховою шириною за допомогою динамічного програмування на шляховій декомпозиції графа. Деревну декомпозицію можна також використовувати для оцінювання ємнісної складності алгоритмів динамічного програмування на графах з обмеженою деревною шириною.
Визначення
У першій відомій серії статей про мінори графа Робертсон і Сеймур визначили шляхову декомпозицію графа G як послідовність підмножин Xi вершин графа G з двома властивостями:
- Для кожного ребра G існує i, таке, що обидві кінцеві точки ребра належать підмножині Xi.
- Для будь-яких трьох індексів i ≤ j ≤ k, Xi ∩ Xk ⊆ Xj.
Друга з цих двох властивостей еквівалентна вимозі, що підмножини, які містять будь-яку вершину, утворюють неперервну підпослідовність усієї послідовності. Мовою пізнішої серії робіт Робертсона і Сеймура про мінори графа, шляхова декомпозиція — це деревна декомпозиція (X,T), в якій дерево T декомпозиції, що лежить нижче, є шляхом.
Ширина шляхової декомпозиції визначається так само, як і для деревної декомпозиції, як maxi |Xi| − 1, а шляхова ширина графа G дорівнює мінімальній ширині всіх шляхових декомпозицій графа G. Віднімання одиниці від розміру Xi в цьому визначенні мало впливає на більшість застосувань шляхової ширини, але зате робить шляхову ширину шляху рівною одиниці.
Альтернативні описи
Як пише Бодлендер шляхову ширину можна описати багатьма еквівалентними способами.
Склеювання послідовностей
Деревну декомпозицію можна описати як послідовність графів Gi, які склеєні шляхом ототожнення пар вершин у сусідніх графах послідовності, і результатом цього склеювання є граф G. Як графи Gi можна взяти породжені підграфи множин Xi у першому визначенні шляхової декомпозиції, зі склеюванням вершин у сусідніх породжених підграфах, якщо ці вершини породжені тією ж самою вершиною з G. З іншого боку можна відновити Xi як множини вершин графів Gi. Ширина деревної декомпозиції тоді на одиницю менша від максимального числа вершин в одному з графів Gi.
Інтервальна товщина
Шляхова ширина будь-якого графа G на одиницю менша від найменшого клікового числа інтервального графа, що містить G як підграф. Тобто для будь-якої деревної декомпозиції графа G можна знайти інтервальний суперграф, і для будь-якого інтервального суперграфа G можна знайти деревну декомпозицію графа G, ширина декомпозиції якої на одиницю менша від клікового числа інтервального графа.
З одного боку, припустимо, що деревна декомпозиція графа G задана. Тоді можна уявити вершини декомпозиції як точки на прямій (в тому порядку, в якому вони входять до шляху) і подати кожну вершину v як замкнутий інтервал, для якого ці точки є кінцевими. Наприклад, нехай (X1, …, Xr) — шляхова декомпозиція графа G, точки на прямій — [1, …, r], тоді подання вершини v — це інтервал . Тоді деревна декомпозиція вершин, що містять v, відповідає кінцевим точкам інтервалу для v. Граф перетинів інтервалів, утворений з вершин G, — це інтервальний граф, що містить G як підграф. Його максимальні кліки задаються множиною інтервалів, що містять точки представлення, і їх розмір найбільшої кліки на одиницю більший від шляхової ширини графа G.
З іншого боку, якщо G — підграф інтервального графа з кліковим числом p+1, то граф G має деревну декомпозицію ширини p, вершини якої задані максимальними кліками інтервального графа. Наприклад, інтервальний граф, показаний з його інтервальним поданням на рисунку, має деревну декомпозицію з п'ятьма вершинами, відповідними п'ятьом максимальним клікам ABC, ACD, CDE, CDF та FG. Розмір максимальної кліки дорівнює трьом, а ширина цієї деревної декомпозиції дорівнює двом.
Ця еквівалентність між шляховою шириною й інтервальною товщиною є тісною аналогією з еквівалентністю між деревною шириною і мінімальним кліковим числом (мінус одиниця) хордального графа, для якого даний граф є підграфом. Інтервальні графи є особливим випадком хордальних графів, а хордальні графи можна подати у вигляді графів перетинів піддерев спільних дерев, що узагальнює підхід, за якого інтервальні графи інтерпретуються як графи перетинів підшляхів шляху.
Величина вершинного поділу
Припустимо, що вершини графа G лінійно впорядковані. Тоді величина вершинного поділу графа G — це найменше число s, таке, що для кожної вершини v максимум s вершин передують v в упорядкуванні, які мають v або одну з наступних за нею вершин в околі. Величина вершинного поділу графа G — це мінімальна величина вершинного поділу будь-якого лінійного впорядкування графа G. Величину вершинного поділу ввели Елліс, Садбороу та Тернер, і вона дорівнює шляховій ширині графа G. Це випливає з раніше згаданої еквівалентності інтервальних графів і клікових чисел — якщо G є підграфом інтервального графа I, поданого (як на рисунку) так, що всі кінці інтервалів різні, то порядок лівих кінців інтервалів графа I мають величину вершинного поділу на одиницю меншу за клікове число графа I. З іншого боку, з лінійного впорядкування графа G можна отримати інтервальне подання, в якому ліва кінцева точка інтервалу для вершини v є позицією в упорядкуванні, а права кінцева точка є позицією сусіда v, який в упорядкуванні останній.
Вершинно-пошукове число
Гра «пошук вершини» на графі — це вид гри переслідування-ухилення, в якій множина переслідувачів спільно намагаються вистежити втікача, який сховався в графі. Переслідувачі розміщуються у вершинах графа, тоді як утікач може перебувати на будь-якому ребрі графа, його місце розташування і ходи переслідувачам не помітні. Під час чергового ходу деякі (або всі) переслідувачі можуть перейти (довільним чином, не обов'язково уздовж ребер) з однієї вершини в іншу, а втікач рухається потім уздовж будь-якого шляху на графі, але не може проходити через зайняті переслідувачами вершини. Втікач спійманий, коли обидва кінці дуги, на якій він перебуває, зайняті переслідувачами. Вершинно-пошукове число графа — це найменше число переслідувачів, необхідних для гарантованого впіймання втікача незалежно від його поведінки. Як показали Кіроузіс і Пападімітріу, вершинно-пошукове число графа дорівнює його інтервальній товщині. Оптимальною стратегією для переслідувачів є ходи, в яких переслідувачі послідовно утворюють розділювальні множини лінійного впорядкування з мінімальною величиною вершинного поділу.
Межі
Будь-який граф з n вершинами і шляховою шириною k має максимум k(n − k + (k − 1)/2)) ребер, і максимальні графи з шляховою шириною k (графи, до яких не можна додати ребро без збільшення шляхової ширини) мають точно таке число ребер. Максимальний граф з шляховою шириною k повинен бути або k-шляхом, або k-гусеницею, тобто одного з двох особливих видів k-дерева. k-дерево — це з точно n − k максимальними кліками, кожна з яких містить k + 1 вершину. В k-дереві, яке саме не є (k + 1)-клікою, кожна максимальна кліка або ділить граф на дві або більше компоненти, або містить одиничну листову вершину, вершину, яка належить тільки одній максимальній кліці. k-шлях — це k-дерево з максимум двома листками, а k-гусениця — це k-дерево, яке можна поділити на k-шлях і множину k-листків, кожен з яких суміжний з сепаратором k-кліки k-шляху. Зокрема, максимальні графи шляхової ширини одиниця — це точно графи-гусениці.
Оскільки шляхові декомпозиції є особливими випадками деревних декомпозицій, шляхова ширина будь-якого графа більша або дорівнює його деревній ширині. Шляхова ширина також менша або дорівнює ширині розрізу, мінімального числа ребер, які перетинають будь-який перетин між вершинами з меншим індексом і великим індексом в оптимальному лінійному впорядкуванні вершин графа. Це випливає з факту, що величина вершинного поділу, число вершин з меншим індексом з сусідами, що мають більший індекс, не більша від числа розрізаючих ребер. З цієї ж причини ширина розрізу не перевищує шляхової ширини, помноженої на максимальний степінь вершин у даному графі.
Будь-який ліс з n вершинами має шляхову ширину O(log n). Для лісу можна завжди знайти стале число вершин, видалення яких приводить до лісу, який можна розбити на два менших ліси з максимум 2n/3 вершин у кожному з цих лісів. Лінійне впорядкування, утворене рекурсивним застосуванням такого розбиття, має логарифмічне пошукове число для вершин. Та сама техніка, застосована до деревної декомпозиції графа, показує, що якщо деревна ширина графа G з n вершинами дорівнює t, то шляхова ширина графа G дорівнює O(t log n). Оскільки зовніпланарні графи, паралельно-послідовні графи та графи Халіна всі мають обмежену деревну ширину, всі вони мають максимум логарифмічну шляхову ширину.
Крім того, що шляхова ширина пов'язана з деревною шириною, вона пов'язана з кліковою шириною і шириною розрізу через реберні графи. Реберний граф L(G) графа G має вершину для кожного ребра графа G і дві вершини в L(G) суміжні, якщо відповідні два ребра G мають спільні кінцеві точки. Будь-яке сімейство графів має обмежену шляхову ширину тоді й лише тоді, коли його реберні графи мають обмежену лінійну клікову ширину, де лінійна клікова ширина замінює операцію об'єднання у визначенні клікової ширини на операцію приєднання окремої нової вершини. Якщо зв'язний граф з трьома або більше вершинами має максимальний степінь 3, його ширина розрізу дорівнює величині вершинного поділу його реберного графа.
В будь-якому планарному графі шляхова ширина в гіршому випадку пропорційна квадратному кореню від кількості вершин. Один зі способів пошуку шляхової декомпозиції з такою шириною — (подібно до шляхової декомпозиції з логарифмічною деревною шириною, описаної вище) використовувати теорему про планарне розбиття, щоб знайти множини з O(√n) вершин, видалення яких розбиває граф на два підграфи з максимум 2n/3 вершинами в кожному, і з'єднати рекурсивно побудовані для цих двох підграфів шляхові декомпозиції. Цю ж техніку можна застосувати до будь-якого класу графів, для яких виконується подібна теорема про розбиття. Оскільки будь-яке сімейство графів, замкнуте щодо взяття мінорів, як і в разі планарних графів, має розбивальну множину вершин розміру O(√n), звідси випливає, що шляхова ширина графів у будь-якому фіксованому замкнутому відносно мінорів сімействі знову дорівнює O(√n). Для деяких класів планарних графів шляхова ширина графа і шляхова ширина його двоїстого графа повинні лежати в інтервалі, межі якого лінійно залежать від значень — такі межі відомі для двозв'язних зовнішніх планарних графів і для графів багатогранників. Для двозв'язних планарних графів шляхова ширина двоїстого графа менша, ніж шляхова ширина реберного графа. Залишається відкритим питання, чи буде шляхова ширина планарного графа і його двоїстого завжди в лінійних межах для інших випадків.
Для деяких класів графів доведено, що шляхова ширина графа і деревна ширина завжди рівні між собою — це виконується для кографів, графів перестановки, доповнень графів порівнянності і графів порівнянностіінтервальних порядків.
Нерозв'язана проблема математики: Яка максимальна шляхова ширина кубічного графа з вершинами? (більше нерозв'язаних проблем математики) |
В будь-якому кубічному графі або, більш загально, будь-якому графі з максимальним степенем вершин 3, шляхова ширина не перевищує n/6 + o(n), де n — кількість вершин графа. Існують кубічні графи зі шляховою шириною 0,082n, але невідомо, як скоротити цей розрив між нижньою межею і верхньою межею n/6.
Обчислення шляхових декомпозицій
Визначення, чи не перевищує шляхова ширина заданого значення k для заданого графа, є NP-повною задачею, якщо k є вхідним параметром. Найвідоміші часові межі обчислення шляхової ширини довільного графа з n вершинами мають вигляд O(2n nc) за деякої константи c. Проте відомі деякі алгоритми обчислення шляхової декомпозиції з більшою ефективністю, якщо шляхова ширина мала, якщо клас вхідних графів обмежений, або потрібно обчислити шляхову ширину приблизно.
Фіксовано-параметрично розв'язність
Шляхова ширина [en] — для будь-якого сталого k можна перевірити, чи не перевершує шляхова ширина величини k, і, якщо не перевершує, знайти шляхову декомпозицію ширини k за лінійний час. У цілому, ці алгоритми працюють у два етапи. На першому етапі використовується припущення, що граф має шляхову ширину k, для пошуку шляхової декомпозиції або деревної декомпозиції. Ця декомпозиція не оптимальна, але її ширина може бути обмежена функцією від k. На другому етапі застосовується алгоритм динамічного програмування для пошуку оптимальної декомпозиції. Однак часові межі для відомих алгоритмів цього типу експоненціальні від k2 і не становлять практичного інтересу, хіба що для малих значень k. Для випадку k = 2 Фляйтер дав алгоритм з лінійним часом роботи, заснований на структурній декомпозиції графів зі шляховою шириною 2.
Особливі класи графів
Бодлендер дав огляд складності задач обчислення шляхової ширини на різних особливих класах графів. Визначення, чи перевищує шляхова ширина графа G величину k, залишається NP-повною задачею, якщо G береться із графів обмеженого степеня, планарних графів, планарних графів обмеженого степеня, хордальних графів, хордальних доміно, доповнень графів порівнянності, і двочасткових дистанційно-успадковуваних графів. Звідси негайно випливає, що задача також NP-повна для сімейств графів, що містять двочасткові дистанційно-успадковувані графи, включно з двочастковими графами, хордальними двочастковими графами, дистанційно-успадковуваними графами та коловими графами.
Однак шляхову ширину можна обчислити за лінійний час для дерев і лісів. Можна обчислити цю величину за поліноміальний час для графів обмеженої деревної ширини, до яких належать паралельно-послідовні графи, зовніпланарні графи і графи Халіна, а також розщеплювані графи, доповнення хордальних графів, графи перестановок, кографи, графи дуг кола, графи порівнянності інтервальних порядків і, звичайно, самі інтервальні графи, оскільки для них шляхова ширина просто на одиницю менша від максимального числа інтервального покриття будь-якої точки в інтервальному поданні графа.
Апроксимаційні алгоритми
NP-складною задачею є апроксимація шляхової ширини графа адитивною константою. Найкращий відомий апроксимаційний коефіцієнт апроксимаційних алгоритмів поліноміального часу для шляхової ширини дорівнює O((log n)3/2). Ранні апроксимаційні алгоритми для шляхової ширини можна знайти у Бодлендера, Гілберта, Хафштейнссона, Клокса і Гуха. Для апроксимації обмежених класів графів див. книгу Клокса і Бодлендера.
Мінори графа
Мінор графа G — це інший граф, створений з G стягуванням ребер, видаленням ребер і вершин. Мінор графа має глибоку теорію, в якій деякі важливі результати використовують шляхову ширину.
Виключення лісу
Якщо сімейство F графів замкнуте відносно операції взяття мінорів (будь-який мінор члена сімейства F також міститься в F), тоді за теоремою Робертсона — Сеймура сімейство F можна схарактеризувати як графи, що не містять мінорів з X, де X — скінченна множина заборонених мінорів. Наприклад, теорема Вагнера стверджує, що планарні графи — це графи, які не містять ні повного графа K5, ні повного двочасткового графа K3,3 як мінорів. У багатьох випадках властивості F і властивості X тісно пов'язані, і перший результат такого типу отримали Робертсон і Сеймур і він пов'язує існування обмеженої шляхової ширини з наявністю лісу в сім'ї заборонених мінорів. Детальніше, визначимо сімейство F графів як таке, що має обмежену шляхову ширину, якщо існує константа p, така, що будь-який граф з F має шляхову ширину, яка не перевищує p. Тоді мінорно-замкнуте сімейство F має обмежену шляхову ширину тоді й лише тоді, коли множина X заборонених мінорів для F включає хоча б один ліс.
З одного боку, цей результат можна довести прямо — а саме, що якщо X не містить хоча б одного лісу, то вільні від X-мінорів графи не мають обмеженої шляхової ширини. В цьому випадку вільні від X-мінорів графи включають усі ліси, і зокрема досконалі бінарні дерева. Але досконалі бінарні дерева з 2k + 1 рівнями мають шляхову ширину k, так що в цьому випадку вільні від X-мінорів графи мають необмежену шляхову ширину. З іншого боку, якщо X містить ліс з n вершинами, то вільні від X-мінорів графи мають шляхову ширину, яка не перевищує n − 2.
Оцінки шляхової ширини
Властивість мати шляхову ширину не більше ніж p є, сама по собі, замкнутою за взяттям мінорів властивістю — якщо G має шляхову декомпозицію з шириною, що не перевищує p, то та ж сама шляхова декомпозиція залишається правильною, якщо видалити будь-яке ребро з G, а також будь-яку вершину можна видалити з графа G і його шляхової декомпозиції без збільшення ширини. Стягування ребра також можна завершити без збільшення ширини декомпозиції злиттям підшляхів, що являють собою два кінці стягуваного ребра. Таким чином, графи зі шляховою шириною, що не перевищує p, можна схарактеризувати множиною Xp заборонених мінорів.
Хоча Xp обов'язково включає щонайменше один ліс, невірно, що всі графи в Xp є лісами. Наприклад, X1 складається з двох графів, дерева з сімома вершинами і трикутника K3. Однак множину дерев у Xp можна точно описати — це точно ті дерева, які можна утворити з трьох дерев із Xp − 1 утворенням нового кореня і з'єднанням його ребрами з довільно вибраними вершинами менших дерев. Наприклад, дерево із сімома вершинами в X1 утворене з дерев з двома вершинами (одне ребро) з X0. Ґрунтуючись на цій побудові, можна показати, що число заборонених мінорів у Xp не менше від (p!)2. Повну множину X2 заборонених мінорів для графів зі шляховою шириною 2 обчислено. Ця множина містить 110 різних графів.
Структурна теорія
Структурна теорема графів сімейств замкнутих за мінорами графів стверджує, що для будь-якого такого сімейства F, його графи можна розкласти на суму за клікою графів, які можна вкласти в поверхні обмеженого роду разом з обмеженим числом верхівок і вихорів для кожної компоненти суми за клікою. Верхівка — це вершина, яка суміжна з усіма вершинами компоненти, а вихор — це граф обмеженої шляхової ширини, що приклеюється до грані компоненти з укладенням обмеженого роду. Циклічний порядок вершин навколо грані, в яку вихор укладено, повинен бути сумісний з деревною декомпозицією вихору в тому сенсі, що розрив циклу для утворення лінійного впорядкування повинен привести до впорядкування з обмеженою величиною вершинного поділу. Ця теорія, в якій шляхова ширина тісно пов'язана з довільними сімействами графів, замкнутих щодо мінорів, має важливе алгоритмічне застосування.
Застосування
НВІС
Під час розробки НВІС задача розділення вершин спочатку вивчалася як шлях поділу ланцюгів на менші підсистеми з малим числом компонент на межі між системами.
Отцукі, Морі, Кух і Кашівабара використовували інтервальну товщину для моделювання числа провідників, необхідних в одновимірному розташуванні ланцюгів НВІС, утворених множиною модулів, які необхідно з'єднати системою мереж. У їхній моделі можна утворити граф, у якому вершини представляють ланцюги і в якому дві вершини з'єднано ребром, якщо їхні ланцюги приєднано до одного у того ж модуля. Тобто якщо модулі й ланцюги розуміються як вершини і гіперребра гіперграфа, то граф, утворений з них, є . Інтервальне подання суперграфа цього реберного графа разом з розфарбуванням суперграфа описує розташування ланцюгів уздовж горизонтальних доріжок (одна доріжка на кожен колір), так що модулі можна розташувати вздовж доріжок у лінійному порядку і з'єднати з потрібними ланцюгами. З факту, що інтервальні графи є досконалими, випливає, що число кольорів, необхідних для оптимальної розкладки такого типу, дорівнює кліковому числу інтервального доповнення графа ланцюгів.
Матрична укладання перемикачів є специфічним видом КМОН НВІС укладання для ланцюгів алгебри логіки. В матричних укладаннях перемикачів сигнал поширюється вздовж «ліній» (вертикальних відрізків), тоді як кожен перемикач утворюється послідовністю елементів, розташованих на горизонтальному відрізку. Таким чином, горизонтальні відрізки для кожного перемикача повинні перетинати вертикальні відрізки для кожної лінії, яка служить входом або виходом перемикача. Як і в укладаннях Отцукі, Морі, Куха і Кашівабара укладання такого типу, що мінімізує число вертикальних прямих, можна знайти, обчисливши шляхову ширину графа, що має прямі як вершини, а пари прямих, що належать перемикачу, як ребра. Той самий алгоритмічний підхід можна також використати для моделювання задач укладання в програмованих логічних інтегральних схемах.
Візуалізація графів
Шляхова ширина має кілька застосувань для візуалізації графів:
- Мінімальні графи, що мають задане число схрещень, мають шляхову ширину, обмежену функцією від числа схрещень.
- Число паралельних прямих, на яких можна розташувати вершини дерева без перетину ребер (за різних природних обмежень на способи, якими суміжні вершини можна помістити на прямих з урахуванням послідовності прямих) пропорційне шляховій ширині дерева.
- k-перетинний h-рівневий малюнок графа G — це розташування вершин графа G на h різних горизонтальних прямих з ребрами у вигляді монотонних (представлених ламаними) шляхів між прямими, в якому є не більше ніж k схрещень. Графи з таким поданням мають шляхову ширину, обмежену функцією від h і k. Таким чином, якщо величини h і k сталі, можна за лінійний час визначити, чи має граф k-перетинний h-рівневий малюнок.
- Граф з n вершинами і шляховою шириною p можна вкласти в тривимірну ґратку розміру p × p × n таким чином, що ніякі два ребра (представлені прямолінійними відрізками між точками ґратки) не перетинаються. Таким чином, графи обмеженої шляхової ширини мають вкладення цього типу з лінійним об'ємом.
Проєктування компіляторів
Під час трансляції високорівневих мов програмування шляхова ширина виникає в задачі переупорядкування лінійного коду (тобто без коду керувальної логіки — переходів і циклів) таким чином, що всі значення, обчислені в коді, можуть бути поміщені в машинні регістри, а не витіснені в основну пам'ять. У цьому застосуванні відтрансльований код подається у вигляді спрямованого ациклічного графа (САГ), у якому вершини представляють вхідні значення коду і значення, обчислені внаслідок операцій усередині коду. Ребро з вершини x у вершину y в цьому САГ представляє факт, що значення x є одним зі вхідних параметрів для операції y. Топологічне сортування вершин у цьому САГ представляє правильне сортування коду, а число регістрів, потрібних для виконання коду в цьому порядку задається величиною вершинного розділення впорядкування.
Для будь-якого фіксованого числа w регістрів у машині можна визначити за лінійний час, чи можна фрагмент лінійного коду переупорядкувати так, що для коду буде потрібно максимум w регістрів. Якщо величина вершинного топологічного розділення впорядкування не перевершує w, мінімальне вершинне розділення серед усіх впорядкувань не може бути більшим, так що неорієнтовані графи, утворені нехтууванням орієнтації САГ, описаного вище, повинні мати шляхову ширину, що не перевершує w. Можна перевірити, чи правильно це за допомогою відомих фіксовано-параметрично розв'язних алгоритмів для шляхової ширини, і, якщо правильно, знайти шляхову декомпозицію для неорієнтованих графів за лінійний час у припущенні, що w є константою. Як тільки деревну декомпозицію знайдено, топологічне сортування з шириною w (якщо таке існує) можна знайти з використанням динамічного програмування, знову ж таки за лінійний час.
Лінгвістика
Карнаї і Туца описали застосування шляхової ширини для обробки природної мови. В цьому застосуванні речення моделюються у вигляді графів, у яких вершини представляють слова, а ребра представляють зв'язки між словами. Наприклад, якщо прикметник модифікує іменник, то граф має ребро між цими двома словами. Через обмежений обсяг короткочасної людської пам'яті Міллер, Корнаї і Туца стверджують, що цей граф повинен мати обмежену шляхову ширину (конкретніше, вони стверджують, що ця шляхова ширина не перевищує шести), в іншому випадку люди не могли б розпізнавати мову правильно.
Експоненційні алгоритми
Багато задачі теорії графів можна ефективно розв'язати на графах з малою шляховою шириною за допомогою динамічного програмування, спираючись на шляхову декомпозицію графа. Наприклад, якщо лінійне упорядкування вершин графа G з n вершинами задано і величина вершинного розділення дорівнює w, то можна знайти найбільшу незалежну множину графа G за час O(2wn). На графі з обмеженою шляховою шириною цей підхід веде до фіксовано-параметрично розв'язних алгоритмів, параметризованих за шляховою шириною. Такі результати не часто зустрічаються в літературі, оскільки вони належать до групи схожих алгоритмів, параметризованих за деревною шириною. Однак шляхова ширина з'являється навіть в алгоритмах динамічного програмування, заснованих на деревній ширині, при вимірюванні просторової складності цих алгоритмів.
Той самий метод динамічного програмування можна застосувати до графів з необмеженою шляховою шириною, що приводить до алгоритмів, які розв'язують непараметризовані задачі на графах за експоненційний час. Наприклад, комбінація підходу динамічного програмування з фактом, що кубічні графи мають шляхову ширину n/6 + o(n), показує, що для кубічних графів максимальну незалежну множину можна побудувати за час O(2n/6 + o(n)), що швидше від відомих до цього методів. Схожий підхід веде до поліпшених алгоритмів експоненційного часу для задач і мінімальної домінівної множини для кубічних графів і для деяких інших NP-складних оптимізаційних задач.
Див. також
- Інтервальна розмірність графа, інший шлях вимірювання складності довільних графів у термінах інтервальних графів
- Деревна глибина — число, яке обмежене для мінорно-замкнутих сімейств графів тоді й лише тоді, коли сімейство не містить шляху
- Виродження, міра розрідженості графа, що не більша від шляхової ширини графа
- [en], інша NP-повна задача оптимізації, яка використовує лінійні укладення графів
- Число Стралера, міра щільності кореневих дерев, що визначається подібно до шляхової ширини неорієнтованих дерев
- Деревна ширина
- Клікова ширина
,
Примітки
- Diestel, Kühn, 2005.
- Robertson, Seymour, 1983.
- Bodlaender, 1998.
- Багато використаних у статті терминів можна знайти у вступі до дисертації Ф. В. Фоміна ((Фомин, 1996))
- Robertson, Seymour, 2003.
- Kashiwabara, Fujisawa, 1979; Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979; Lengauer, 1981; Arnborg, Corneil, Proskurowski, 1987.
- Bodlaender, Gilbert, Hafsteinsson, Kloks, 1992.
- Bodlaender, 1994.
- Möhring, 1990; Scheffler, 1990; Ellis, Sudborough, Turner, 1994; Coudert, Huc, Mazauric, 1998; Peng, Ho, Hsu, Ko, Tang, 1998; Skodinis, 2000; Skodinis, (2003).
- Arnborg, 1985.
- Aspvall, Proskurowski, Telle, 2000.
- Bodlaender, 1994, с. 1–2.
- Bodlaender, 1998, с. 13, Theorem 29.
- Ellis, Sudborough, Turner, 1983.
- Kinnersley, 1992.
- Bodlaender, 1998, с. Theorem 51.
- Kirousis, Papadimitriou, 1985.
- Proskurowski, Telle, 1999.
- Korach, Solel, 1993, с. 99, Lemma 3.
- Bodlaender, 1998, с. 24, Theorem 47.
- Korach, Solel, 1993, с. 99, Lemma 1.
- Bodlaender, 1998, с. 24, Theorem 49.
- Korach, Solel, 1993, с. 99, Theorem 5.
- Bodlaender, 1998, с. 30, Theorem 66.
- Шеффлер (Scheffler, (1992)) дає сильнішу межу log3(2n + 1) шляхової ширини лісу з n вершинами.
- Korach, Solel, 1993, с. 100, Theorem 6.
- Bodlaender, 1998, с. 10, Corollary 24.
- Gurski, Wanke, 2007.
- Golovach, 1993.
- Bodlaender, 1998, с. 10, Corollary 23.
- Bodlaender, 1998, с. 9, Theorem 20.
- Alon, Seymour, Thomas, 1990.
- Bodlaender, Fomin, 2002.
- Coudert, Huc, Sereni, 2007.
- Fomin, Thilikos, 2007.
- Amini, Huc, Pérennes, 2009.
- Fomin, 2003.
- Bodlaender, Möhring, 1990.
- Bodlaender, Kloks, Kratsch, 1993.
- Habib, Möhring, 1994.
- Garbe, 1995.
- Fomin, Høie, 2006.
- Fomin, Kratsch, Todinca, Villanger, 2008.
- Downey, Fellows, 1999, с. 12.
- de Fluiter, 1997.
- Monien, Sudborough, 1988.
- Gusted, 1993.
- Kloks, Kratsch, Müller, 1995. Хордальне доміно — це хордальний граф, у якому будь-яка вершина належить максимум двом максимальним клікам
- Kloks, Bodlaender, Müller, Kratsch, 1993.
- Bodlaender, (1996); Bodlaender, Kloks, (1996)
- Kloks, Bodlaender, 1992.
- Гарбе (Garbe, (1995)) приписує цей результат тезам дисертації Тона Клокса 1993 року. Алгоритм поліноміального часу Гарбе для графів порівнянності інтервальных упорядкувань узагальнює цей результат, оскільки будь-який хордальний граф має бути графом порівнянності такого типу.
- Suchan, Todinca, 2007.
- Feige, Hajiaghayi, Lee, 2005.
- Guha, 2000.
- Robertson, Seymour, 2004.
- Bienstock, Robertson, Seymour, Thomas, 1991.
- Diestel, 1995.
- Cattell, Dinneen, Fellows, 1996.
- Takahashi, Ueno, Kajitani, 1994.
- Bodlaender, 1998, с. 8.
- Kinnersley, Langston, 1994.
- Demaine, Hajiaghayi, Kawarabayashi, 2005.
- Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979.
- Berge, 1967.
- Lopez, Law, 1980.
- Fellows, Langston, 1989.
- Möhring, 1990.
- Ferreira, Song, 1992.
- Hliněny, 2003.
- Suderman, 2004.
- Dujmović, Fellows, Kitching и др., 2008.
- Dujmović, Morin, Wood, 2003.
- Bodlaender, Gustedt, Telle, 1998.
- Kornai, Tuza, 1992.
- Miller, 1956.
- Kneis, Mölle, Richter, Rossmanith, 2005.
- Björklund, Husfeldt, 2008.
Література
- Noga Alon, Paul Seymour, Robin Thomas. Proc. 22nd ACM Symp. on Theory of Computing (STOC 1990). — 1990. — С. 293—299. — . — DOI:10.1145/100216.100254..
- Omid Amini, Florian Huc, Stéphane Pérennes. On the path-width of planar graphs // SIAM Journal on Discrete Mathematics. — 2009. — Т. 23, вип. 3. — С. 1311—1316. — DOI:10.1137/060670146..
- Stefan Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey // BIT. — 1985. — Т. 25, вип. 1. — С. 2—23. — DOI:10.1007/BF01934985..
- Stefan Arnborg, Derek G. Corneil, Andrzej Proskurowski. Complexity of finding embeddings in a $k$-tree // SIAM Journal on Algebraic and Discrete Methods. — 1987. — Т. 8, вип. 2. — С. 277—284. — DOI:10.1137/0608024..
- Bengt Aspvall, Andrzej Proskurowski, Jan Arne Telle. Memory requirements for table computations in partial k-tree algorithms // . — 2000. — Т. 27, вип. 3. — С. 382—394. — DOI:10.1007/s004530010025..
- Claude Berge. Graph Theory and Theoretical Physics. — New York : Academic Press, 1967. — С. 155—165..
- Dan Bienstock, Neil Robertson, Paul Seymour, Robin Thomas. Quickly excluding a forest // . — 1991. — Т. 52, вип. 2. — С. 274—283. — DOI:10.1016/0095-8956(91)90068-U..
- Andreas Björklund, Thore Husfeldt. Exact algorithms for exact satisfiability and number of perfect matchings // . — 2008. — Т. 52, вип. 2. — С. 226—249. — DOI:10.1007/s00453-007-9149-8..
- Hans L. Bodlaender. A tourist guide through treewidth // Acta Cybernetica. — 1994. — Т. 11.
- Hans L. Bodlaender. Developments in Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 November 1992) / Jürgen Dassow, Alisa Kelemenová. — Gordon and Breach, 1994. — Т. 6. — С. 1—20. — (Topics in Computer Mathematics)..
- Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth // . — 1996. — Т. 25, вип. 6. — С. 1305—1317. — DOI:10.1137/S0097539793251219..
- Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth : ( )[англ.] // [en]. — 1998. — Vol. 209, no. 1—2. — С. 1—45. — DOI:10.1016/S0304-3975(97)00228-4..
- Hans L. Bodlaender, Fedor V. Fomin. Approximation of pathwidth of outerplanar graphs // Journal of Algorithms. — 2002. — Т. 43, вип. 2. — С. 190—200. — DOI:10.1016/S0196-6774(02)00001-9..
- Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, Ton Kloks. Graph-Theoretic Concepts in Computer Science. — 1992. — Т. 570. — С. 1—12. — (). — . — DOI:10.1007/3-540-55121-2_1..
- Hans L. Bodlaender, Jens Gustedt, Jan Arne Telle. Proc. 9th ACM–SIAM Symposium on Discrete Algorithms (SODA '98). — 1998. — С. 574—583..
- Hans L. Bodlaender, Ton Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs // Journal of Algorithms. — 1996. — Т. 21, вип. 2. — С. 358—402. — DOI:10.1006/jagm.1996.0049..
- Hans L. Bodlaender, Ton Kloks, Dieter Kratsch. . — Springer-Verlag, 1993. — Т. 700. — С. 114—125. — (Lecture Notes in Computer Science). — . — DOI:10.1007/3-540-56939-1_66..
- Hans L. Bodlaender, Rolf H. Möhring. . — Springer-Verlag, 1990. — Т. 447. — С. 301—309. — (Lecture Notes in Computer Science). — . — DOI:10.1007/3-540-52846-6_99..
- Kevin Cattell, Michael J. Dinneen, Michael R. Fellows. A simple linear-time algorithm for finding path-decompositions of small width // . — 1996. — Т. 57, вип. 4. — С. 197—203. — DOI:10.1016/0020-0190(95)00190-5..
- David Coudert, Florian Huc, Dorian Mazauric. Proc. 22nd Int. Symp. Distributed Computing. — Springer-Verlag, 1998. — Т. 5218. — С. 500—501. — (Lecture Notes in Computer Science). — . — DOI:10.1007/978-3-540-87779-0_36..
- David Coudert, Florian Huc, Jean-Sébastien Sereni. Pathwidth of outerplanar graphs // . — 2007. — Т. 55, вип. 1. — С. 27—41. — DOI:10.1002/jgt.20218..
- Reinhard Diestel. Graph Minors I: a short proof of the path-width theorem // . — 1995. — Т. 4, вип. 1. — С. 27—30. — DOI:10.1017/S0963548300001450..
- Reinhard Diestel, Daniela Kühn. Graph minor hierarchies // . — 2005. — Т. 145, вип. 2. — С. 167—182. — DOI:10.1016/j.dam.2004.01.010..
- Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi. . — 2005. — С. 637—646. — . — DOI:10.1109/SFCS.2005.14..
- Rod G. Downey, Michael R. Fellows. Parameterized Complexity. — Springer-Verlag, 1999. — ..
- V. Dujmović, M.R. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, S. Whitesides, David R. Wood. On the parameterized complexity of layered graph drawing // . — 2008. — Т. 52, вип. 2. — С. 267—292. — DOI:10.1007/s00453-007-9151-1..
- Vida Dujmović, Pat Morin, David R. Wood. Proc. 10th International Symposium on Graph Drawing (GD 2002). — Springer-Verlag, 2003. — Т. 2528. — С. 42—53. — (Lecture Notes in Computer Science)..
- J. A. Ellis, I. H. Sudborough, J. S. Turner. Proc. 1983 Allerton Conf. on Communication, Control, and Computing. — 1983.. As cited by Monien та Sudborough, (1988).
- J. A. Ellis, I. H. Sudborough, J. S. Turner. The vertex separation and search number of a tree // . — 1994. — Т. 113, вип. 1. — С. 50—79. — DOI:10.1006/inco.1994.1064..
- Uriel Feige, Mohammadtaghi Hajiaghayi, James R. Lee. . — 2005. — С. 563—572. — . — DOI:10.1145/1060590.1060674..
- Michael R. Fellows, Michael A. Langston. . — 1989. — С. 501—512. — . — DOI:10.1145/73007.73055..
- Afonso G. Ferreira, Siang W. Song. Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92). — Springer-Verlag, 1992. — Т. 583. — С. 139—153. — (Lecture Notes in Computer Science). — . — DOI:10.1007/BFb0023825..
- Babette de Fluiter. . — , 1997. — (Ph.D. thesis). — ..
- Fedor V. Fomin. Pathwidth of planar and line graphs // . — 2003. — Т. 19, вип. 1. — С. 91—99. — DOI:10.1007/s00373-002-0490-z..
- Fedor V. Fomin, Kjartan Høie. Pathwidth of cubic graphs and exact algorithms // . — 2006. — Т. 97, вип. 5. — С. 191—196. — DOI:10.1016/j.ipl.2005.10.012..
- Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, Yngve Villanger. Exact algorithms for treewidth and minimum fill-in // . — 2008. — Т. 38, вип. 3. — С. 1058—1079. — DOI:10.1137/050643350..
- Fedor V. Fomin, Dimitrios M. Thilikos. On self duality of pathwidth in polyhedral graph embeddings // . — 2007. — Т. 55, вип. 1. — С. 42—54. — DOI:10.1002/jgt.20219..
- Renate Garbe. Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94). — Springer-Verlag, 1995. — Т. 903. — С. 26—37. — (Lecture Notes in Computer Science). — . — DOI:10.1007/3-540-59071-4_35..
- P. A. Golovach. The cutwidth of a graph and the vertex separation number of the line graph // Discrete Mathematics and Applications. — 1993. — Т. 3, вип. 5. — С. 517—522. — DOI:10.1515/dma.1993.3.5.517..
- Sudipto Guha. . — 2000. — С. 126. — . — DOI:10.1109/SFCS.2000.892072..
- Frank Gurski, Egon Wanke. Line graphs of bounded clique-width // . — 2007. — Т. 307, вип. 22. — С. 2734—2754. — DOI:10.1016/j.disc.2007.01.020..
- Jens Gusted. On the pathwidth of chordal graphs // . — 1993. — Т. 45, вип. 3. — С. 233—248. — DOI:10.1016/0166-218X(93)90012-D..
- Michel Habib, Rolf H. Möhring. Treewidth of cocomparability graphs and a new order-theoretic parameter // . — 1994. — Т. 11, вип. 1. — С. 47—60. — DOI:10.1007/BF01462229..
- Petr Hliněny. Crossing-number critical graphs have bounded path-width // . — 2003. — Т. 88, вип. 2. — С. 347—367. — DOI:10.1016/S0095-8956(03)00037-6..
- T. Kashiwabara, T. Fujisawa. . — 1979. — С. 657—660..
- Nancy G. Kinnersley. The vertex separation number of a graph equals its path-width // . — 1992. — Т. 42, вип. 6. — С. 345—350. — DOI:10.1016/0020-0190(92)90234-M..
- Nancy G. Kinnersley, Michael A. Langston. Obstruction set isolation for the gate matrix layout problem // . — 1994. — Т. 54, вип. 2—3. — С. 169—213. — DOI:10.1016/0166-218X(94)90021-3..
- Lefteris M. Kirousis, Christos H. Papadimitriou. Interval graphs and searching // . — 1985. — Т. 55, вип. 2. — С. 181—184. — DOI:10.1016/0012-365X(85)90046-9.[недоступне посилання з Ноябрь 2017].
- Ton Kloks, Hans L. Bodlaender. Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92). — Springer-Verlag, 1992. — Т. 650. — С. 116—125. — (Lecture Notes in Computer Science). — . — DOI:10.1007/3-540-56279-6_64..
- T. Kloks, H. Bodlaender, H. Müller, D. Kratsch. . — Springer-Verlag, 1993. — Т. 726. — С. 260—271. — (Lecture Notes in Computer Science). — DOI:10.1007/3-540-57273-2_61..
- Ton Kloks, Dieter Kratsch, H. Müller. Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94). — Springer-Verlag, 1995. — Т. 903. — С. 106—120. — (Lecture Notes in Computer Science). — . — DOI:10.1007/3-540-59071-4_41..
- Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith. Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005). — Springer-Verlag, 2005. — Т. 3787. — С. 385—396. — (Lecture Notes in Computer Science). — . — DOI:10.1007/11604686_34..
- Ephraim Korach, Nir Solel. Tree-width, path-width, and cutwidth // . — 1993. — Т. 43, вип. 1. — С. 97—101. — DOI:10.1016/0166-218X(93)90171-J..
- András Kornai, Zsolt Tuza. Narrowness, path-width, and their application in natural language processing // . — 1992. — Т. 36, вип. 1. — С. 87—92. — DOI:10.1016/0166-218X(92)90208-R..
- Thomas Lengauer. Black-white pebbles and graph separation // . — 1981. — Т. 16, вип. 4. — С. 465—475. — DOI:10.1007/BF00264496..
- Alexander D. Lopez, Hung-Fai S. Law. A dense gate matrix layout method for MOS VLSI // IEEE Transactions on Electron Devices. — 1980. — Т. ED—27, вип. 8. — С. 1671—1675. — DOI:10.1109/T-ED.1980.20086..
- George A. Miller. The Magical Number Seven, Plus or Minus Two // . — 1956. — Т. 63, вип. 2. — С. 81—97. — DOI:10.1037/h0043158. — PMID 13310704..
- Rolf H. Möhring. Computational Graph Theory / G. Tinhofer, E. Mayr, H. Noltemeier, M. Sysło. — Springer-Verlag, 1990. — Т. 7. — С. 17—51. — (Computing Supplementum). — ..
- B. Monien, I. H. Sudborough. Min cut is NP-complete for edge weighted trees : ( )[англ.] // [en]. — 1988. — Vol. 58, no. 1—3. — С. 209—229. — DOI:10.1016/0304-3975(88)90028-X..
- Tatsuo Ohtsuki, Hajimu Mori, Ernest S. Kuh, Toshinobu Kashiwabara, Toshio Fujisawa. One-dimensional logic gate assignment and interval graphs // IEEE Transactions on Circuits and Systems. — 1979. — Т. 26, вип. 9. — С. 675—684. — DOI:10.1109/TCS.1979.1084695..
- Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, Chuan Yi Tang. Proc. 4th Int. Conf. Computing and Combinatorics (COCOON'98). — Springer-Verlag, 1998. — Т. 1449. — С. 197—205. — (Lecture Notes in Computer Science)..
- Andrzej Proskurowski, Jan Arne Telle. Classes of graphs with restricted interval models : ( )[англ.] // [en]. — 1999. — Vol. 3. — С. 167—176..
- Neil Robertson, Paul Seymour. Graph minors. I. Excluding a forest // . — 1983. — Т. 35, вип. 1. — С. 39—61. — DOI:10.1016/0095-8956(83)90079-5..
- Neil Robertson, Paul Seymour. Graph minors. XVI. Excluding a non-planar graph // . — 2003. — Т. 89, вип. 1. — С. 43—76. — DOI:10.1016/S0095-8956(03)00042-X..
- Neil Robertson, Paul D. Seymour. Graph Minors. XX. Wagner's conjecture // . — 2004. — Т. 92, вип. 2. — С. 325—357. — DOI:10.1016/j.jctb.2004.08.001..
- Petra Scheffler. Topics in Combinatorics and Graph Theory / R. Bodendiek, R. Henn. — Physica-Verlag, 1990. — С. 613—620..
- Petra Scheffler. Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity / Jaroslav Nešetřil, Miroslav Fiedler. — Elsevier, 1992..
- Konstantin Skodinis. . — Springer-Verlag, 2000. — Т. 1879. — С. 403—414. — (Lecture Notes in Computer Science). — . — DOI:10.1007/3-540-45253-2_37..
- Konstantin Skodinis. Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time // Journal of Algorithms. — 2003. — Т. 47, вип. 1. — С. 40—59. — DOI:10.1016/S0196-6774(02)00225-0..
- Karol Suchan, Ioan Todinca. Proc. 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007). — Springer-Verlag, 2007. — Т. 4769. — С. 258—269. — (Lecture Notes in Computer Science). — DOI:10.1007/978-3-540-74839-7_25..
- Matthew Suderman. Pathwidth and layered drawings of trees : [ 3 травня 2003] // . — 2004. — Т. 14, вип. 3. — С. 203—225. — DOI:10.1142/S0218195904001433..
- Atsushi Takahashi, Shuichi Ueno, Yoji Kajitani. Minimal acyclic forbidden minors for the family of graphs with bounded path-width // . — 1994. — Т. 127, вип. 1—3. — С. 293—304. — DOI:10.1016/0012-365X(94)90092-2..
- Ф.В. Фомин. Задачи преследования и поиска на графах // Электронная библиотека диссертаций. — 1996.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi grafiv shlyahova dekompoziciya grafa G ce neformalno podannya grafa G u viglyadi potovshenogo shlyahu a shlyahova shirina grafa G ce chislo sho vimiryuye naskilki graf G buv potovshenij Formalnishe shlyahova dekompoziciya ce poslidovnosti vershin pidmnozhini grafa G taki sho kincevi vershini kozhnogo rebra z yavlyayutsya v odnij z pidmnozhin i kozhna vershina nalezhit hocha b odnij mnozhini a shlyahova shirina na odinicyu mensha vid rozmiru najbilshoyi mnozhini v cij dekompoziciyi Shlyahova shirina vidoma takozh yak intervalna tovshina na odinicyu menshe vid rozmiru najbilshoyi kliki intervalnogo supergrafa grafa G velichina vershinnogo rozdilennya chi vershinno poshukove chislo Shlyahova shirina i shlyahova dekompoziciya ye tisnoyu analogiyeyu z derevnoyu shirinoyu i derevnoyu dekompoziciyeyu Voni vidigrayut klyuchovu rol u teoriyi minoriv grafa simejstva grafiv yaki zamknuti vidnosno minoriv grafa i ne vklyuchayut usi dereva mozhna sharakterizuvati yak taki sho mayut obmezhenu shlyahovu shirinu i vihori sho vinikayut u zagalnij strukturnij teoriyi simejstv grafiv zamknutih za minorom mayut obmezhenu shlyahovu shirinu Shlyahova shirina i grafi z obmezhenoyu shlyahovoyu shirinoyu zastosovuyutsya v rozrobci NVIS vizualizaciyi grafiv ta komp yuternij lingvistici Zadacha znahodzhennya shlyahovoyi shirini dovilnih grafiv ye NP skladnoyu Bilshe togo NP skladnoyu ye navit zadacha aproksimaciyi shlyahovoyi shirini tochno Odnak cya zadacha ye fiksovano parametrichno rozv yaznoyu perevirku chi maye graf shlyahovu shirinu k mozhna zdijsniti za chas yakij linijno zalezhit vid rozmiru grafa ale supereksponencialno vid k Krim togo dlya deyakih osoblivih klasiv grafiv takih yak dereva shlyahovu shirinu mozhna obchisliti za polinomialnij chas ne zalezhnij vid k Bagato zadach teoriyi grafiv mozhna efektivno rozv yazati na grafah z obmezhenoyu shlyahovoyu shirinoyu za dopomogoyu dinamichnogo programuvannya na shlyahovij dekompoziciyi grafa Derevnu dekompoziciyu mozhna takozh vikoristovuvati dlya ocinyuvannya yemnisnoyi skladnosti algoritmiv dinamichnogo programuvannya na grafah z obmezhenoyu derevnoyu shirinoyu ViznachennyaPriklad grafa G z shlyahovoyu shirinoyu 2 i jogo shlyahova dekompoziciya shirini 2 U nizhnij chastini risunka navedeno toj samij graf i shlyahova dekompoziciya z dodanimi kolorami dlya viraznosti Cej priklad uzyato z knigi Bodlendera i dodano kolori U pershij vidomij seriyi statej pro minori grafa Robertson i Sejmur viznachili shlyahovu dekompoziciyu grafa G yak poslidovnist pidmnozhin Xi vershin grafa G z dvoma vlastivostyami Dlya kozhnogo rebra G isnuye i take sho obidvi kincevi tochki rebra nalezhat pidmnozhini Xi Dlya bud yakih troh indeksiv i j k Xi Xk Xj Druga z cih dvoh vlastivostej ekvivalentna vimozi sho pidmnozhini yaki mistyat bud yaku vershinu utvoryuyut neperervnu pidposlidovnist usiyeyi poslidovnosti Movoyu piznishoyi seriyi robit Robertsona i Sejmura pro minori grafa shlyahova dekompoziciya ce derevna dekompoziciya X T v yakij derevo T dekompoziciyi sho lezhit nizhche ye shlyahom Shirina shlyahovoyi dekompoziciyi viznachayetsya tak samo yak i dlya derevnoyi dekompoziciyi yak maxi Xi 1 a shlyahova shirina grafa G dorivnyuye minimalnij shirini vsih shlyahovih dekompozicij grafa G Vidnimannya odinici vid rozmiru Xi v comu viznachenni malo vplivaye na bilshist zastosuvan shlyahovoyi shirini ale zate robit shlyahovu shirinu shlyahu rivnoyu odinici Alternativni opisiYak pishe Bodlender shlyahovu shirinu mozhna opisati bagatma ekvivalentnimi sposobami Skleyuvannya poslidovnostej Derevnu dekompoziciyu mozhna opisati yak poslidovnist grafiv Gi yaki skleyeni shlyahom ototozhnennya par vershin u susidnih grafah poslidovnosti i rezultatom cogo skleyuvannya ye graf G Yak grafi Gi mozhna vzyati porodzheni pidgrafi mnozhin Xi u pershomu viznachenni shlyahovoyi dekompoziciyi zi skleyuvannyam vershin u susidnih porodzhenih pidgrafah yaksho ci vershini porodzheni tiyeyu zh samoyu vershinoyu z G Z inshogo boku mozhna vidnoviti Xi yak mnozhini vershin grafiv Gi Shirina derevnoyi dekompoziciyi todi na odinicyu mensha vid maksimalnogo chisla vershin v odnomu z grafiv Gi Intervalna tovshina Intervalnij graf z shlyahovoyu shirinoyu dva na odinicyu menshoyu vid chisla chotiroh maksimalnih klik ABC ACD CDE i CDF Shlyahova shirina bud yakogo grafa G na odinicyu mensha vid najmenshogo klikovogo chisla intervalnogo grafa sho mistit G yak pidgraf Tobto dlya bud yakoyi derevnoyi dekompoziciyi grafa G mozhna znajti intervalnij supergraf i dlya bud yakogo intervalnogo supergrafa G mozhna znajti derevnu dekompoziciyu grafa G shirina dekompoziciyi yakoyi na odinicyu mensha vid klikovogo chisla intervalnogo grafa Z odnogo boku pripustimo sho derevna dekompoziciya grafa G zadana Todi mozhna uyaviti vershini dekompoziciyi yak tochki na pryamij v tomu poryadku v yakomu voni vhodyat do shlyahu i podati kozhnu vershinu v yak zamknutij interval dlya yakogo ci tochki ye kincevimi Napriklad nehaj X1 Xr shlyahova dekompoziciya grafa G tochki na pryamij 1 r todi podannya vershini v ce interval min i v Xi max i v Xi displaystyle min i v in X i max i v in X i Todi derevna dekompoziciya vershin sho mistyat v vidpovidaye kincevim tochkam intervalu dlya v Graf peretiniv intervaliv utvorenij z vershin G ce intervalnij graf sho mistit G yak pidgraf Jogo maksimalni kliki zadayutsya mnozhinoyu intervaliv sho mistyat tochki predstavlennya i yih rozmir najbilshoyi kliki na odinicyu bilshij vid shlyahovoyi shirini grafa G Z inshogo boku yaksho G pidgraf intervalnogo grafa z klikovim chislom p 1 to graf G maye derevnu dekompoziciyu shirini p vershini yakoyi zadani maksimalnimi klikami intervalnogo grafa Napriklad intervalnij graf pokazanij z jogo intervalnim podannyam na risunku maye derevnu dekompoziciyu z p yatma vershinami vidpovidnimi p yatom maksimalnim klikam ABC ACD CDE CDF ta FG Rozmir maksimalnoyi kliki dorivnyuye trom a shirina ciyeyi derevnoyi dekompoziciyi dorivnyuye dvom Cya ekvivalentnist mizh shlyahovoyu shirinoyu j intervalnoyu tovshinoyu ye tisnoyu analogiyeyu z ekvivalentnistyu mizh derevnoyu shirinoyu i minimalnim klikovim chislom minus odinicya hordalnogo grafa dlya yakogo danij graf ye pidgrafom Intervalni grafi ye osoblivim vipadkom hordalnih grafiv a hordalni grafi mozhna podati u viglyadi grafiv peretiniv pidderev spilnih derev sho uzagalnyuye pidhid za yakogo intervalni grafi interpretuyutsya yak grafi peretiniv pidshlyahiv shlyahu Velichina vershinnogo podilu Pripustimo sho vershini grafa G linijno vporyadkovani Todi velichina vershinnogo podilu grafa G ce najmenshe chislo s take sho dlya kozhnoyi vershini v maksimum s vershin pereduyut v v uporyadkuvanni yaki mayut v abo odnu z nastupnih za neyu vershin v okoli Velichina vershinnogo podilu grafa G ce minimalna velichina vershinnogo podilu bud yakogo linijnogo vporyadkuvannya grafa G Velichinu vershinnogo podilu vveli Ellis Sadborou ta Terner i vona dorivnyuye shlyahovij shirini grafa G Ce viplivaye z ranishe zgadanoyi ekvivalentnosti intervalnih grafiv i klikovih chisel yaksho G ye pidgrafom intervalnogo grafa I podanogo yak na risunku tak sho vsi kinci intervaliv rizni to poryadok livih kinciv intervaliv grafa I mayut velichinu vershinnogo podilu na odinicyu menshu za klikove chislo grafa I Z inshogo boku z linijnogo vporyadkuvannya grafa G mozhna otrimati intervalne podannya v yakomu liva kinceva tochka intervalu dlya vershini v ye poziciyeyu v uporyadkuvanni a prava kinceva tochka ye poziciyeyu susida v yakij v uporyadkuvanni ostannij Vershinno poshukove chislo Gra poshuk vershini na grafi ce vid gri peresliduvannya uhilennya v yakij mnozhina peresliduvachiv spilno namagayutsya vistezhiti vtikacha yakij shovavsya v grafi Peresliduvachi rozmishuyutsya u vershinah grafa todi yak utikach mozhe perebuvati na bud yakomu rebri grafa jogo misce roztashuvannya i hodi peresliduvacham ne pomitni Pid chas chergovogo hodu deyaki abo vsi peresliduvachi mozhut perejti dovilnim chinom ne obov yazkovo uzdovzh reber z odniyeyi vershini v inshu a vtikach ruhayetsya potim uzdovzh bud yakogo shlyahu na grafi ale ne mozhe prohoditi cherez zajnyati peresliduvachami vershini Vtikach spijmanij koli obidva kinci dugi na yakij vin perebuvaye zajnyati peresliduvachami Vershinno poshukove chislo grafa ce najmenshe chislo peresliduvachiv neobhidnih dlya garantovanogo vpijmannya vtikacha nezalezhno vid jogo povedinki Yak pokazali Kirouzis i Papadimitriu vershinno poshukove chislo grafa dorivnyuye jogo intervalnij tovshini Optimalnoyu strategiyeyu dlya peresliduvachiv ye hodi v yakih peresliduvachi poslidovno utvoryuyut rozdilyuvalni mnozhini linijnogo vporyadkuvannya z minimalnoyu velichinoyu vershinnogo podilu MezhiGraf gusenicya maksimalnij graf z shlyahovoyu shirinoyu odin Bud yakij graf z n vershinami i shlyahovoyu shirinoyu k maye maksimum k n k k 1 2 reber i maksimalni grafi z shlyahovoyu shirinoyu k grafi do yakih ne mozhna dodati rebro bez zbilshennya shlyahovoyi shirini mayut tochno take chislo reber Maksimalnij graf z shlyahovoyu shirinoyu k povinen buti abo k shlyahom abo k guseniceyu tobto odnogo z dvoh osoblivih vidiv k dereva k derevo ce z tochno n k maksimalnimi klikami kozhna z yakih mistit k 1 vershinu V k derevi yake same ne ye k 1 klikoyu kozhna maksimalna klika abo dilit graf na dvi abo bilshe komponenti abo mistit odinichnu listovu vershinu vershinu yaka nalezhit tilki odnij maksimalnij klici k shlyah ce k derevo z maksimum dvoma listkami a k gusenicya ce k derevo yake mozhna podiliti na k shlyah i mnozhinu k listkiv kozhen z yakih sumizhnij z separatorom k kliki k shlyahu Zokrema maksimalni grafi shlyahovoyi shirini odinicya ce tochno grafi gusenici Oskilki shlyahovi dekompoziciyi ye osoblivimi vipadkami derevnih dekompozicij shlyahova shirina bud yakogo grafa bilsha abo dorivnyuye jogo derevnij shirini Shlyahova shirina takozh mensha abo dorivnyuye shirini rozrizu minimalnogo chisla reber yaki peretinayut bud yakij peretin mizh vershinami z menshim indeksom i velikim indeksom v optimalnomu linijnomu vporyadkuvanni vershin grafa Ce viplivaye z faktu sho velichina vershinnogo podilu chislo vershin z menshim indeksom z susidami sho mayut bilshij indeks ne bilsha vid chisla rozrizayuchih reber Z ciyeyi zh prichini shirina rozrizu ne perevishuye shlyahovoyi shirini pomnozhenoyi na maksimalnij stepin vershin u danomu grafi Bud yakij lis z n vershinami maye shlyahovu shirinu O log n Dlya lisu mozhna zavzhdi znajti stale chislo vershin vidalennya yakih privodit do lisu yakij mozhna rozbiti na dva menshih lisi z maksimum 2n 3 vershin u kozhnomu z cih lisiv Linijne vporyadkuvannya utvorene rekursivnim zastosuvannyam takogo rozbittya maye logarifmichne poshukove chislo dlya vershin Ta sama tehnika zastosovana do derevnoyi dekompoziciyi grafa pokazuye sho yaksho derevna shirina grafa G z n vershinami dorivnyuye t to shlyahova shirina grafa G dorivnyuye O t log n Oskilki zovniplanarni grafi paralelno poslidovni grafi ta grafi Halina vsi mayut obmezhenu derevnu shirinu vsi voni mayut maksimum logarifmichnu shlyahovu shirinu Krim togo sho shlyahova shirina pov yazana z derevnoyu shirinoyu vona pov yazana z klikovoyu shirinoyu i shirinoyu rozrizu cherez reberni grafi Rebernij graf L G grafa G maye vershinu dlya kozhnogo rebra grafa G i dvi vershini v L G sumizhni yaksho vidpovidni dva rebra G mayut spilni kincevi tochki Bud yake simejstvo grafiv maye obmezhenu shlyahovu shirinu todi j lishe todi koli jogo reberni grafi mayut obmezhenu linijnu klikovu shirinu de linijna klikova shirina zaminyuye operaciyu ob yednannya u viznachenni klikovoyi shirini na operaciyu priyednannya okremoyi novoyi vershini Yaksho zv yaznij graf z troma abo bilshe vershinami maye maksimalnij stepin 3 jogo shirina rozrizu dorivnyuye velichini vershinnogo podilu jogo rebernogo grafa V bud yakomu planarnomu grafi shlyahova shirina v girshomu vipadku proporcijna kvadratnomu korenyu vid kilkosti vershin Odin zi sposobiv poshuku shlyahovoyi dekompoziciyi z takoyu shirinoyu podibno do shlyahovoyi dekompoziciyi z logarifmichnoyu derevnoyu shirinoyu opisanoyi vishe vikoristovuvati teoremu pro planarne rozbittya shob znajti mnozhini z O n vershin vidalennya yakih rozbivaye graf na dva pidgrafi z maksimum 2n 3 vershinami v kozhnomu i z yednati rekursivno pobudovani dlya cih dvoh pidgrafiv shlyahovi dekompoziciyi Cyu zh tehniku mozhna zastosuvati do bud yakogo klasu grafiv dlya yakih vikonuyetsya podibna teorema pro rozbittya Oskilki bud yake simejstvo grafiv zamknute shodo vzyattya minoriv yak i v razi planarnih grafiv maye rozbivalnu mnozhinu vershin rozmiru O n zvidsi viplivaye sho shlyahova shirina grafiv u bud yakomu fiksovanomu zamknutomu vidnosno minoriv simejstvi znovu dorivnyuye O n Dlya deyakih klasiv planarnih grafiv shlyahova shirina grafa i shlyahova shirina jogo dvoyistogo grafa povinni lezhati v intervali mezhi yakogo linijno zalezhat vid znachen taki mezhi vidomi dlya dvozv yaznih zovnishnih planarnih grafiv i dlya grafiv bagatogrannikiv Dlya dvozv yaznih planarnih grafiv shlyahova shirina dvoyistogo grafa mensha nizh shlyahova shirina rebernogo grafa Zalishayetsya vidkritim pitannya chi bude shlyahova shirina planarnogo grafa i jogo dvoyistogo zavzhdi v linijnih mezhah dlya inshih vipadkiv Dlya deyakih klasiv grafiv dovedeno sho shlyahova shirina grafa i derevna shirina zavzhdi rivni mizh soboyu ce vikonuyetsya dlya kografiv grafiv perestanovki dopovnen grafiv porivnyannosti i grafiv porivnyannostiintervalnih poryadkiv Nerozv yazana problema matematiki Yaka maksimalna shlyahova shirina kubichnogo grafa z n displaystyle n vershinami bilshe nerozv yazanih problem matematiki V bud yakomu kubichnomu grafi abo bilsh zagalno bud yakomu grafi z maksimalnim stepenem vershin 3 shlyahova shirina ne perevishuye n 6 o n de n kilkist vershin grafa Isnuyut kubichni grafi zi shlyahovoyu shirinoyu 0 082n ale nevidomo yak skorotiti cej rozriv mizh nizhnoyu mezheyu i verhnoyu mezheyu n 6 Obchislennya shlyahovih dekompozicijViznachennya chi ne perevishuye shlyahova shirina zadanogo znachennya k dlya zadanogo grafa ye NP povnoyu zadacheyu yaksho k ye vhidnim parametrom Najvidomishi chasovi mezhi obchislennya shlyahovoyi shirini dovilnogo grafa z n vershinami mayut viglyad O 2n nc za deyakoyi konstanti c Prote vidomi deyaki algoritmi obchislennya shlyahovoyi dekompoziciyi z bilshoyu efektivnistyu yaksho shlyahova shirina mala yaksho klas vhidnih grafiv obmezhenij abo potribno obchisliti shlyahovu shirinu priblizno Fiksovano parametrichno rozv yaznist Shlyahova shirina en dlya bud yakogo stalogo k mozhna pereviriti chi ne perevershuye shlyahova shirina velichini k i yaksho ne perevershuye znajti shlyahovu dekompoziciyu shirini k za linijnij chas U cilomu ci algoritmi pracyuyut u dva etapi Na pershomu etapi vikoristovuyetsya pripushennya sho graf maye shlyahovu shirinu k dlya poshuku shlyahovoyi dekompoziciyi abo derevnoyi dekompoziciyi Cya dekompoziciya ne optimalna ale yiyi shirina mozhe buti obmezhena funkciyeyu vid k Na drugomu etapi zastosovuyetsya algoritm dinamichnogo programuvannya dlya poshuku optimalnoyi dekompoziciyi Odnak chasovi mezhi dlya vidomih algoritmiv cogo tipu eksponencialni vid k2 i ne stanovlyat praktichnogo interesu hiba sho dlya malih znachen k Dlya vipadku k 2 Flyajter dav algoritm z linijnim chasom roboti zasnovanij na strukturnij dekompoziciyi grafiv zi shlyahovoyu shirinoyu 2 Osoblivi klasi grafiv Bodlender dav oglyad skladnosti zadach obchislennya shlyahovoyi shirini na riznih osoblivih klasah grafiv Viznachennya chi perevishuye shlyahova shirina grafa G velichinu k zalishayetsya NP povnoyu zadacheyu yaksho G beretsya iz grafiv obmezhenogo stepenya planarnih grafiv planarnih grafiv obmezhenogo stepenya hordalnih grafiv hordalnih domino dopovnen grafiv porivnyannosti i dvochastkovih distancijno uspadkovuvanih grafiv Zvidsi negajno viplivaye sho zadacha takozh NP povna dlya simejstv grafiv sho mistyat dvochastkovi distancijno uspadkovuvani grafi vklyuchno z dvochastkovimi grafami hordalnimi dvochastkovimi grafami distancijno uspadkovuvanimi grafami ta kolovimi grafami Odnak shlyahovu shirinu mozhna obchisliti za linijnij chas dlya derev i lisiv Mozhna obchisliti cyu velichinu za polinomialnij chas dlya grafiv obmezhenoyi derevnoyi shirini do yakih nalezhat paralelno poslidovni grafi zovniplanarni grafi i grafi Halina a takozh rozsheplyuvani grafi dopovnennya hordalnih grafiv grafi perestanovok kografi grafi dug kola grafi porivnyannosti intervalnih poryadkiv i zvichajno sami intervalni grafi oskilki dlya nih shlyahova shirina prosto na odinicyu mensha vid maksimalnogo chisla intervalnogo pokrittya bud yakoyi tochki v intervalnomu podanni grafa Aproksimacijni algoritmi Dokladnishe Aproksimacijnij algoritm NP skladnoyu zadacheyu ye aproksimaciya shlyahovoyi shirini grafa aditivnoyu konstantoyu Najkrashij vidomij aproksimacijnij koeficiyent aproksimacijnih algoritmiv polinomialnogo chasu dlya shlyahovoyi shirini dorivnyuye O log n 3 2 Ranni aproksimacijni algoritmi dlya shlyahovoyi shirini mozhna znajti u Bodlendera Gilberta Hafshtejnssona Kloksa i Guha Dlya aproksimaciyi obmezhenih klasiv grafiv div knigu Kloksa i Bodlendera Minori grafaMinor grafa G ce inshij graf stvorenij z G styaguvannyam reber vidalennyam reber i vershin Minor grafa maye gliboku teoriyu v yakij deyaki vazhlivi rezultati vikoristovuyut shlyahovu shirinu Viklyuchennya lisu Yaksho simejstvo F grafiv zamknute vidnosno operaciyi vzyattya minoriv bud yakij minor chlena simejstva F takozh mistitsya v F todi za teoremoyu Robertsona Sejmura simejstvo F mozhna sharakterizuvati yak grafi sho ne mistyat minoriv z X de X skinchenna mnozhina zaboronenih minoriv Napriklad teorema Vagnera stverdzhuye sho planarni grafi ce grafi yaki ne mistyat ni povnogo grafa K5 ni povnogo dvochastkovogo grafa K3 3 yak minoriv U bagatoh vipadkah vlastivosti F i vlastivosti X tisno pov yazani i pershij rezultat takogo tipu otrimali Robertson i Sejmur i vin pov yazuye isnuvannya obmezhenoyi shlyahovoyi shirini z nayavnistyu lisu v sim yi zaboronenih minoriv Detalnishe viznachimo simejstvo F grafiv yak take sho maye obmezhenu shlyahovu shirinu yaksho isnuye konstanta p taka sho bud yakij graf z F maye shlyahovu shirinu yaka ne perevishuye p Todi minorno zamknute simejstvo F maye obmezhenu shlyahovu shirinu todi j lishe todi koli mnozhina X zaboronenih minoriv dlya F vklyuchaye hocha b odin lis Z odnogo boku cej rezultat mozhna dovesti pryamo a same sho yaksho X ne mistit hocha b odnogo lisu to vilni vid X minoriv grafi ne mayut obmezhenoyi shlyahovoyi shirini V comu vipadku vilni vid X minoriv grafi vklyuchayut usi lisi i zokrema doskonali binarni dereva Ale doskonali binarni dereva z 2k 1 rivnyami mayut shlyahovu shirinu k tak sho v comu vipadku vilni vid X minoriv grafi mayut neobmezhenu shlyahovu shirinu Z inshogo boku yaksho X mistit lis z n vershinami to vilni vid X minoriv grafi mayut shlyahovu shirinu yaka ne perevishuye n 2 Ocinki shlyahovoyi shirini Zaboroneni minori dlya grafiv z shlyahovoyu shirinoyu 1 Vlastivist mati shlyahovu shirinu ne bilshe nizh p ye sama po sobi zamknutoyu za vzyattyam minoriv vlastivistyu yaksho G maye shlyahovu dekompoziciyu z shirinoyu sho ne perevishuye p to ta zh sama shlyahova dekompoziciya zalishayetsya pravilnoyu yaksho vidaliti bud yake rebro z G a takozh bud yaku vershinu mozhna vidaliti z grafa G i jogo shlyahovoyi dekompoziciyi bez zbilshennya shirini Styaguvannya rebra takozh mozhna zavershiti bez zbilshennya shirini dekompoziciyi zlittyam pidshlyahiv sho yavlyayut soboyu dva kinci styaguvanogo rebra Takim chinom grafi zi shlyahovoyu shirinoyu sho ne perevishuye p mozhna sharakterizuvati mnozhinoyu Xp zaboronenih minoriv Hocha Xp obov yazkovo vklyuchaye shonajmenshe odin lis nevirno sho vsi grafi v Xp ye lisami Napriklad X1 skladayetsya z dvoh grafiv dereva z simoma vershinami i trikutnika K3 Odnak mnozhinu derev u Xp mozhna tochno opisati ce tochno ti dereva yaki mozhna utvoriti z troh derev iz Xp 1 utvorennyam novogo korenya i z yednannyam jogo rebrami z dovilno vibranimi vershinami menshih derev Napriklad derevo iz simoma vershinami v X1 utvorene z derev z dvoma vershinami odne rebro z X0 Gruntuyuchis na cij pobudovi mozhna pokazati sho chislo zaboronenih minoriv u Xp ne menshe vid p 2 Povnu mnozhinu X2 zaboronenih minoriv dlya grafiv zi shlyahovoyu shirinoyu 2 obchisleno Cya mnozhina mistit 110 riznih grafiv Strukturna teoriya Strukturna teorema grafiv simejstv zamknutih za minorami grafiv stverdzhuye sho dlya bud yakogo takogo simejstva F jogo grafi mozhna rozklasti na sumu za klikoyu grafiv yaki mozhna vklasti v poverhni obmezhenogo rodu razom z obmezhenim chislom verhivok i vihoriv dlya kozhnoyi komponenti sumi za klikoyu Verhivka ce vershina yaka sumizhna z usima vershinami komponenti a vihor ce graf obmezhenoyi shlyahovoyi shirini sho prikleyuyetsya do grani komponenti z ukladennyam obmezhenogo rodu Ciklichnij poryadok vershin navkolo grani v yaku vihor ukladeno povinen buti sumisnij z derevnoyu dekompoziciyeyu vihoru v tomu sensi sho rozriv ciklu dlya utvorennya linijnogo vporyadkuvannya povinen privesti do vporyadkuvannya z obmezhenoyu velichinoyu vershinnogo podilu Cya teoriya v yakij shlyahova shirina tisno pov yazana z dovilnimi simejstvami grafiv zamknutih shodo minoriv maye vazhlive algoritmichne zastosuvannya ZastosuvannyaNVIS Pid chas rozrobki NVIS zadacha rozdilennya vershin spochatku vivchalasya yak shlyah podilu lancyugiv na menshi pidsistemi z malim chislom komponent na mezhi mizh sistemami Otcuki Mori Kuh i Kashivabara vikoristovuvali intervalnu tovshinu dlya modelyuvannya chisla providnikiv neobhidnih v odnovimirnomu roztashuvanni lancyugiv NVIS utvorenih mnozhinoyu moduliv yaki neobhidno z yednati sistemoyu merezh U yihnij modeli mozhna utvoriti graf u yakomu vershini predstavlyayut lancyugi i v yakomu dvi vershini z yednano rebrom yaksho yihni lancyugi priyednano do odnogo u togo zh modulya Tobto yaksho moduli j lancyugi rozumiyutsya yak vershini i giperrebra gipergrafa to graf utvorenij z nih ye Intervalne podannya supergrafa cogo rebernogo grafa razom z rozfarbuvannyam supergrafa opisuye roztashuvannya lancyugiv uzdovzh gorizontalnih dorizhok odna dorizhka na kozhen kolir tak sho moduli mozhna roztashuvati vzdovzh dorizhok u linijnomu poryadku i z yednati z potribnimi lancyugami Z faktu sho intervalni grafi ye doskonalimi viplivaye sho chislo koloriv neobhidnih dlya optimalnoyi rozkladki takogo tipu dorivnyuye klikovomu chislu intervalnogo dopovnennya grafa lancyugiv Matrichna ukladannya peremikachiv ye specifichnim vidom KMON NVIS ukladannya dlya lancyugiv algebri logiki V matrichnih ukladannyah peremikachiv signal poshiryuyetsya vzdovzh linij vertikalnih vidrizkiv todi yak kozhen peremikach utvoryuyetsya poslidovnistyu elementiv roztashovanih na gorizontalnomu vidrizku Takim chinom gorizontalni vidrizki dlya kozhnogo peremikacha povinni peretinati vertikalni vidrizki dlya kozhnoyi liniyi yaka sluzhit vhodom abo vihodom peremikacha Yak i v ukladannyah Otcuki Mori Kuha i Kashivabara ukladannya takogo tipu sho minimizuye chislo vertikalnih pryamih mozhna znajti obchislivshi shlyahovu shirinu grafa sho maye pryami yak vershini a pari pryamih sho nalezhat peremikachu yak rebra Toj samij algoritmichnij pidhid mozhna takozh vikoristati dlya modelyuvannya zadach ukladannya v programovanih logichnih integralnih shemah Vizualizaciya grafiv Shlyahova shirina maye kilka zastosuvan dlya vizualizaciyi grafiv Minimalni grafi sho mayut zadane chislo shreshen mayut shlyahovu shirinu obmezhenu funkciyeyu vid chisla shreshen Chislo paralelnih pryamih na yakih mozhna roztashuvati vershini dereva bez peretinu reber za riznih prirodnih obmezhen na sposobi yakimi sumizhni vershini mozhna pomistiti na pryamih z urahuvannyam poslidovnosti pryamih proporcijne shlyahovij shirini dereva k peretinnij h rivnevij malyunok grafa G ce roztashuvannya vershin grafa G na h riznih gorizontalnih pryamih z rebrami u viglyadi monotonnih predstavlenih lamanimi shlyahiv mizh pryamimi v yakomu ye ne bilshe nizh k shreshen Grafi z takim podannyam mayut shlyahovu shirinu obmezhenu funkciyeyu vid h i k Takim chinom yaksho velichini h i k stali mozhna za linijnij chas viznachiti chi maye graf k peretinnij h rivnevij malyunok Graf z n vershinami i shlyahovoyu shirinoyu p mozhna vklasti v trivimirnu gratku rozmiru p p n takim chinom sho niyaki dva rebra predstavleni pryamolinijnimi vidrizkami mizh tochkami gratki ne peretinayutsya Takim chinom grafi obmezhenoyi shlyahovoyi shirini mayut vkladennya cogo tipu z linijnim ob yemom Proyektuvannya kompilyatoriv Pid chas translyaciyi visokorivnevih mov programuvannya shlyahova shirina vinikaye v zadachi pereuporyadkuvannya linijnogo kodu tobto bez kodu keruvalnoyi logiki perehodiv i cikliv takim chinom sho vsi znachennya obchisleni v kodi mozhut buti pomisheni v mashinni registri a ne vitisneni v osnovnu pam yat U comu zastosuvanni vidtranslovanij kod podayetsya u viglyadi spryamovanogo aciklichnogo grafa SAG u yakomu vershini predstavlyayut vhidni znachennya kodu i znachennya obchisleni vnaslidok operacij useredini kodu Rebro z vershini x u vershinu y v comu SAG predstavlyaye fakt sho znachennya x ye odnim zi vhidnih parametriv dlya operaciyi y Topologichne sortuvannya vershin u comu SAG predstavlyaye pravilne sortuvannya kodu a chislo registriv potribnih dlya vikonannya kodu v comu poryadku zadayetsya velichinoyu vershinnogo rozdilennya vporyadkuvannya Dlya bud yakogo fiksovanogo chisla w registriv u mashini mozhna viznachiti za linijnij chas chi mozhna fragment linijnogo kodu pereuporyadkuvati tak sho dlya kodu bude potribno maksimum w registriv Yaksho velichina vershinnogo topologichnogo rozdilennya vporyadkuvannya ne perevershuye w minimalne vershinne rozdilennya sered usih vporyadkuvan ne mozhe buti bilshim tak sho neoriyentovani grafi utvoreni nehtuuvannyam oriyentaciyi SAG opisanogo vishe povinni mati shlyahovu shirinu sho ne perevershuye w Mozhna pereviriti chi pravilno ce za dopomogoyu vidomih fiksovano parametrichno rozv yaznih algoritmiv dlya shlyahovoyi shirini i yaksho pravilno znajti shlyahovu dekompoziciyu dlya neoriyentovanih grafiv za linijnij chas u pripushenni sho w ye konstantoyu Yak tilki derevnu dekompoziciyu znajdeno topologichne sortuvannya z shirinoyu w yaksho take isnuye mozhna znajti z vikoristannyam dinamichnogo programuvannya znovu zh taki za linijnij chas Lingvistika Karnayi i Tuca opisali zastosuvannya shlyahovoyi shirini dlya obrobki prirodnoyi movi V comu zastosuvanni rechennya modelyuyutsya u viglyadi grafiv u yakih vershini predstavlyayut slova a rebra predstavlyayut zv yazki mizh slovami Napriklad yaksho prikmetnik modifikuye imennik to graf maye rebro mizh cimi dvoma slovami Cherez obmezhenij obsyag korotkochasnoyi lyudskoyi pam yati Miller Kornayi i Tuca stverdzhuyut sho cej graf povinen mati obmezhenu shlyahovu shirinu konkretnishe voni stverdzhuyut sho cya shlyahova shirina ne perevishuye shesti v inshomu vipadku lyudi ne mogli b rozpiznavati movu pravilno Eksponencijni algoritmi Bagato zadachi teoriyi grafiv mozhna efektivno rozv yazati na grafah z maloyu shlyahovoyu shirinoyu za dopomogoyu dinamichnogo programuvannya spirayuchis na shlyahovu dekompoziciyu grafa Napriklad yaksho linijne uporyadkuvannya vershin grafa G z n vershinami zadano i velichina vershinnogo rozdilennya dorivnyuye w to mozhna znajti najbilshu nezalezhnu mnozhinu grafa G za chas O 2wn Na grafi z obmezhenoyu shlyahovoyu shirinoyu cej pidhid vede do fiksovano parametrichno rozv yaznih algoritmiv parametrizovanih za shlyahovoyu shirinoyu Taki rezultati ne chasto zustrichayutsya v literaturi oskilki voni nalezhat do grupi shozhih algoritmiv parametrizovanih za derevnoyu shirinoyu Odnak shlyahova shirina z yavlyayetsya navit v algoritmah dinamichnogo programuvannya zasnovanih na derevnij shirini pri vimiryuvanni prostorovoyi skladnosti cih algoritmiv Toj samij metod dinamichnogo programuvannya mozhna zastosuvati do grafiv z neobmezhenoyu shlyahovoyu shirinoyu sho privodit do algoritmiv yaki rozv yazuyut neparametrizovani zadachi na grafah za eksponencijnij chas Napriklad kombinaciya pidhodu dinamichnogo programuvannya z faktom sho kubichni grafi mayut shlyahovu shirinu n 6 o n pokazuye sho dlya kubichnih grafiv maksimalnu nezalezhnu mnozhinu mozhna pobuduvati za chas O 2n 6 o n sho shvidshe vid vidomih do cogo metodiv Shozhij pidhid vede do polipshenih algoritmiv eksponencijnogo chasu dlya zadach i minimalnoyi dominivnoyi mnozhini dlya kubichnih grafiv i dlya deyakih inshih NP skladnih optimizacijnih zadach Div takozhIntervalna rozmirnist grafa inshij shlyah vimiryuvannya skladnosti dovilnih grafiv u terminah intervalnih grafiv Derevna glibina chislo yake obmezhene dlya minorno zamknutih simejstv grafiv todi j lishe todi koli simejstvo ne mistit shlyahu Virodzhennya mira rozridzhenosti grafa sho ne bilsha vid shlyahovoyi shirini grafa en insha NP povna zadacha optimizaciyi yaka vikoristovuye linijni ukladennya grafiv Chislo Stralera mira shilnosti korenevih derev sho viznachayetsya podibno do shlyahovoyi shirini neoriyentovanih derev Derevna shirina Klikova shirina PrimitkiDiestel Kuhn 2005 Robertson Seymour 1983 Bodlaender 1998 Bagato vikoristanih u statti terminiv mozhna znajti u vstupi do disertaciyi F V Fomina Fomin 1996 Robertson Seymour 2003 Kashiwabara Fujisawa 1979 Ohtsuki Mori Kuh Kashiwabara Fujisawa 1979 Lengauer 1981 Arnborg Corneil Proskurowski 1987 Bodlaender Gilbert Hafsteinsson Kloks 1992 Bodlaender 1994 Mohring 1990 Scheffler 1990 Ellis Sudborough Turner 1994 Coudert Huc Mazauric 1998 Peng Ho Hsu Ko Tang 1998 Skodinis 2000 Skodinis 2003 Arnborg 1985 Aspvall Proskurowski Telle 2000 Bodlaender 1994 s 1 2 Bodlaender 1998 s 13 Theorem 29 Ellis Sudborough Turner 1983 Kinnersley 1992 Bodlaender 1998 s Theorem 51 Kirousis Papadimitriou 1985 Proskurowski Telle 1999 Korach Solel 1993 s 99 Lemma 3 Bodlaender 1998 s 24 Theorem 47 Korach Solel 1993 s 99 Lemma 1 Bodlaender 1998 s 24 Theorem 49 Korach Solel 1993 s 99 Theorem 5 Bodlaender 1998 s 30 Theorem 66 Sheffler Scheffler 1992 daye silnishu mezhu log3 2n 1 shlyahovoyi shirini lisu z n vershinami Korach Solel 1993 s 100 Theorem 6 Bodlaender 1998 s 10 Corollary 24 Gurski Wanke 2007 Golovach 1993 Bodlaender 1998 s 10 Corollary 23 Bodlaender 1998 s 9 Theorem 20 Alon Seymour Thomas 1990 Bodlaender Fomin 2002 Coudert Huc Sereni 2007 Fomin Thilikos 2007 Amini Huc Perennes 2009 Fomin 2003 Bodlaender Mohring 1990 Bodlaender Kloks Kratsch 1993 Habib Mohring 1994 Garbe 1995 Fomin Hoie 2006 Fomin Kratsch Todinca Villanger 2008 Downey Fellows 1999 s 12 de Fluiter 1997 Monien Sudborough 1988 Gusted 1993 Kloks Kratsch Muller 1995 Hordalne domino ce hordalnij graf u yakomu bud yaka vershina nalezhit maksimum dvom maksimalnim klikam Kloks Bodlaender Muller Kratsch 1993 Bodlaender 1996 Bodlaender Kloks 1996 Kloks Bodlaender 1992 Garbe Garbe 1995 pripisuye cej rezultat tezam disertaciyi Tona Kloksa 1993 roku Algoritm polinomialnogo chasu Garbe dlya grafiv porivnyannosti intervalnyh uporyadkuvan uzagalnyuye cej rezultat oskilki bud yakij hordalnij graf maye buti grafom porivnyannosti takogo tipu Suchan Todinca 2007 Feige Hajiaghayi Lee 2005 Guha 2000 Robertson Seymour 2004 Bienstock Robertson Seymour Thomas 1991 Diestel 1995 Cattell Dinneen Fellows 1996 Takahashi Ueno Kajitani 1994 Bodlaender 1998 s 8 Kinnersley Langston 1994 Demaine Hajiaghayi Kawarabayashi 2005 Ohtsuki Mori Kuh Kashiwabara Fujisawa 1979 Berge 1967 Lopez Law 1980 Fellows Langston 1989 Mohring 1990 Ferreira Song 1992 Hlineny 2003 Suderman 2004 Dujmovic Fellows Kitching i dr 2008 Dujmovic Morin Wood 2003 Bodlaender Gustedt Telle 1998 Kornai Tuza 1992 Miller 1956 Kneis Molle Richter Rossmanith 2005 Bjorklund Husfeldt 2008 LiteraturaNoga Alon Paul Seymour Robin Thomas Proc 22nd ACM Symp on Theory of Computing STOC 1990 1990 S 293 299 ISBN 0897913612 DOI 10 1145 100216 100254 Omid Amini Florian Huc Stephane Perennes On the path width of planar graphs SIAM Journal on Discrete Mathematics 2009 T 23 vip 3 S 1311 1316 DOI 10 1137 060670146 Stefan Arnborg Efficient algorithms for combinatorial problems on graphs with bounded decomposability A survey BIT 1985 T 25 vip 1 S 2 23 DOI 10 1007 BF01934985 Stefan Arnborg Derek G Corneil Andrzej Proskurowski Complexity of finding embeddings in a k tree SIAM Journal on Algebraic and Discrete Methods 1987 T 8 vip 2 S 277 284 DOI 10 1137 0608024 Bengt Aspvall Andrzej Proskurowski Jan Arne Telle Memory requirements for table computations in partial k tree algorithms 2000 T 27 vip 3 S 382 394 DOI 10 1007 s004530010025 Claude Berge Graph Theory and Theoretical Physics New York Academic Press 1967 S 155 165 Dan Bienstock Neil Robertson Paul Seymour Robin Thomas Quickly excluding a forest 1991 T 52 vip 2 S 274 283 DOI 10 1016 0095 8956 91 90068 U Andreas Bjorklund Thore Husfeldt Exact algorithms for exact satisfiability and number of perfect matchings 2008 T 52 vip 2 S 226 249 DOI 10 1007 s00453 007 9149 8 Hans L Bodlaender A tourist guide through treewidth Acta Cybernetica 1994 T 11 Hans L Bodlaender Developments in Theoretical Computer Science Proc 7th International Meeting of Young Computer Scientists Smolenice 16 20 November 1992 Jurgen Dassow Alisa Kelemenova Gordon and Breach 1994 T 6 S 1 20 Topics in Computer Mathematics Hans L Bodlaender A linear time algorithm for finding tree decompositions of small treewidth 1996 T 25 vip 6 S 1305 1317 DOI 10 1137 S0097539793251219 Hans L Bodlaender A partial k arboretum of graphs with bounded treewidth angl en 1998 Vol 209 no 1 2 S 1 45 DOI 10 1016 S0304 3975 97 00228 4 Hans L Bodlaender Fedor V Fomin Approximation of pathwidth of outerplanar graphs Journal of Algorithms 2002 T 43 vip 2 S 190 200 DOI 10 1016 S0196 6774 02 00001 9 Hans L Bodlaender John R Gilbert Hjalmtyr Hafsteinsson Ton Kloks Graph Theoretic Concepts in Computer Science 1992 T 570 S 1 12 ISBN 978 3 540 55121 8 DOI 10 1007 3 540 55121 2 1 Hans L Bodlaender Jens Gustedt Jan Arne Telle Proc 9th ACM SIAM Symposium on Discrete Algorithms SODA 98 1998 S 574 583 Hans L Bodlaender Ton Kloks Efficient and constructive algorithms for the pathwidth and treewidth of graphs Journal of Algorithms 1996 T 21 vip 2 S 358 402 DOI 10 1006 jagm 1996 0049 Hans L Bodlaender Ton Kloks Dieter Kratsch Springer Verlag 1993 T 700 S 114 125 Lecture Notes in Computer Science ISBN 978 3 540 56939 8 DOI 10 1007 3 540 56939 1 66 Hans L Bodlaender Rolf H Mohring Springer Verlag 1990 T 447 S 301 309 Lecture Notes in Computer Science ISBN 978 3 540 52846 3 DOI 10 1007 3 540 52846 6 99 Kevin Cattell Michael J Dinneen Michael R Fellows A simple linear time algorithm for finding path decompositions of small width 1996 T 57 vip 4 S 197 203 DOI 10 1016 0020 0190 95 00190 5 David Coudert Florian Huc Dorian Mazauric Proc 22nd Int Symp Distributed Computing Springer Verlag 1998 T 5218 S 500 501 Lecture Notes in Computer Science ISBN 978 3 540 87778 3 DOI 10 1007 978 3 540 87779 0 36 David Coudert Florian Huc Jean Sebastien Sereni Pathwidth of outerplanar graphs 2007 T 55 vip 1 S 27 41 DOI 10 1002 jgt 20218 Reinhard Diestel Graph Minors I a short proof of the path width theorem 1995 T 4 vip 1 S 27 30 DOI 10 1017 S0963548300001450 Reinhard Diestel Daniela Kuhn Graph minor hierarchies 2005 T 145 vip 2 S 167 182 DOI 10 1016 j dam 2004 01 010 Erik D Demaine MohammadTaghi Hajiaghayi Ken ichi Kawarabayashi 2005 S 637 646 ISBN 0 7695 2468 0 DOI 10 1109 SFCS 2005 14 Rod G Downey Michael R Fellows Parameterized Complexity Springer Verlag 1999 ISBN 0 387 94883 X V Dujmovic M R Fellows M Kitching G Liotta C McCartin N Nishimura P Ragde F Rosamond S Whitesides David R Wood On the parameterized complexity of layered graph drawing 2008 T 52 vip 2 S 267 292 DOI 10 1007 s00453 007 9151 1 Vida Dujmovic Pat Morin David R Wood Proc 10th International Symposium on Graph Drawing GD 2002 Springer Verlag 2003 T 2528 S 42 53 Lecture Notes in Computer Science J A Ellis I H Sudborough J S Turner Proc 1983 Allerton Conf on Communication Control and Computing 1983 As cited by Monien ta Sudborough 1988 J A Ellis I H Sudborough J S Turner The vertex separation and search number of a tree 1994 T 113 vip 1 S 50 79 DOI 10 1006 inco 1994 1064 Uriel Feige Mohammadtaghi Hajiaghayi James R Lee 2005 S 563 572 ISBN 1581139608 DOI 10 1145 1060590 1060674 Michael R Fellows Michael A Langston 1989 S 501 512 ISBN 0897913078 DOI 10 1145 73007 73055 Afonso G Ferreira Siang W Song Proc 1st Latin American Symposium on Theoretical Informatics LATIN 92 Springer Verlag 1992 T 583 S 139 153 Lecture Notes in Computer Science ISBN 3 540 55284 7 DOI 10 1007 BFb0023825 Babette de Fluiter 1997 Ph D thesis ISBN 90 393 1528 0 Fedor V Fomin Pathwidth of planar and line graphs 2003 T 19 vip 1 S 91 99 DOI 10 1007 s00373 002 0490 z Fedor V Fomin Kjartan Hoie Pathwidth of cubic graphs and exact algorithms 2006 T 97 vip 5 S 191 196 DOI 10 1016 j ipl 2005 10 012 Fedor V Fomin Dieter Kratsch Ioan Todinca Yngve Villanger Exact algorithms for treewidth and minimum fill in 2008 T 38 vip 3 S 1058 1079 DOI 10 1137 050643350 Fedor V Fomin Dimitrios M Thilikos On self duality of pathwidth in polyhedral graph embeddings 2007 T 55 vip 1 S 42 54 DOI 10 1002 jgt 20219 Renate Garbe Proc 20th International Workshop Graph Theoretic Concepts in Computer Science WG 94 Springer Verlag 1995 T 903 S 26 37 Lecture Notes in Computer Science ISBN 978 3 540 59071 2 DOI 10 1007 3 540 59071 4 35 P A Golovach The cutwidth of a graph and the vertex separation number of the line graph Discrete Mathematics and Applications 1993 T 3 vip 5 S 517 522 DOI 10 1515 dma 1993 3 5 517 Sudipto Guha 2000 S 126 ISBN 0 7695 0850 2 DOI 10 1109 SFCS 2000 892072 Frank Gurski Egon Wanke Line graphs of bounded clique width 2007 T 307 vip 22 S 2734 2754 DOI 10 1016 j disc 2007 01 020 Jens Gusted On the pathwidth of chordal graphs 1993 T 45 vip 3 S 233 248 DOI 10 1016 0166 218X 93 90012 D Michel Habib Rolf H Mohring Treewidth of cocomparability graphs and a new order theoretic parameter 1994 T 11 vip 1 S 47 60 DOI 10 1007 BF01462229 Petr Hlineny Crossing number critical graphs have bounded path width 2003 T 88 vip 2 S 347 367 DOI 10 1016 S0095 8956 03 00037 6 T Kashiwabara T Fujisawa 1979 S 657 660 Nancy G Kinnersley The vertex separation number of a graph equals its path width 1992 T 42 vip 6 S 345 350 DOI 10 1016 0020 0190 92 90234 M Nancy G Kinnersley Michael A Langston Obstruction set isolation for the gate matrix layout problem 1994 T 54 vip 2 3 S 169 213 DOI 10 1016 0166 218X 94 90021 3 Lefteris M Kirousis Christos H Papadimitriou Interval graphs and searching 1985 T 55 vip 2 S 181 184 DOI 10 1016 0012 365X 85 90046 9 nedostupne posilannya z Noyabr 2017 Ton Kloks Hans L Bodlaender Proc 3rd International Symposium on Algorithms and Computation ISAAC 92 Springer Verlag 1992 T 650 S 116 125 Lecture Notes in Computer Science ISBN 978 3 540 56279 5 DOI 10 1007 3 540 56279 6 64 T Kloks H Bodlaender H Muller D Kratsch Springer Verlag 1993 T 726 S 260 271 Lecture Notes in Computer Science DOI 10 1007 3 540 57273 2 61 Ton Kloks Dieter Kratsch H Muller Proc 20th International Workshop Graph Theoretic Concepts in Computer Science WG 94 Springer Verlag 1995 T 903 S 106 120 Lecture Notes in Computer Science ISBN 978 3 540 59071 2 DOI 10 1007 3 540 59071 4 41 Joachim Kneis Daniel Molle Stefan Richter Peter Rossmanith Proc 31st International Workshop on Graph Theoretic Concepts in Computer Science WG 2005 Springer Verlag 2005 T 3787 S 385 396 Lecture Notes in Computer Science ISBN 978 3 540 31000 6 DOI 10 1007 11604686 34 Ephraim Korach Nir Solel Tree width path width and cutwidth 1993 T 43 vip 1 S 97 101 DOI 10 1016 0166 218X 93 90171 J Andras Kornai Zsolt Tuza Narrowness path width and their application in natural language processing 1992 T 36 vip 1 S 87 92 DOI 10 1016 0166 218X 92 90208 R Thomas Lengauer Black white pebbles and graph separation 1981 T 16 vip 4 S 465 475 DOI 10 1007 BF00264496 Alexander D Lopez Hung Fai S Law A dense gate matrix layout method for MOS VLSI IEEE Transactions on Electron Devices 1980 T ED 27 vip 8 S 1671 1675 DOI 10 1109 T ED 1980 20086 George A Miller The Magical Number Seven Plus or Minus Two 1956 T 63 vip 2 S 81 97 DOI 10 1037 h0043158 PMID 13310704 Rolf H Mohring Computational Graph Theory G Tinhofer E Mayr H Noltemeier M Syslo Springer Verlag 1990 T 7 S 17 51 Computing Supplementum ISBN 3 211 82177 5 B Monien I H Sudborough Min cut is NP complete for edge weighted trees angl en 1988 Vol 58 no 1 3 S 209 229 DOI 10 1016 0304 3975 88 90028 X Tatsuo Ohtsuki Hajimu Mori Ernest S Kuh Toshinobu Kashiwabara Toshio Fujisawa One dimensional logic gate assignment and interval graphs IEEE Transactions on Circuits and Systems 1979 T 26 vip 9 S 675 684 DOI 10 1109 TCS 1979 1084695 Sheng Lung Peng Chin Wen Ho Tsan sheng Hsu Ming Tat Ko Chuan Yi Tang Proc 4th Int Conf Computing and Combinatorics COCOON 98 Springer Verlag 1998 T 1449 S 197 205 Lecture Notes in Computer Science Andrzej Proskurowski Jan Arne Telle Classes of graphs with restricted interval models angl en 1999 Vol 3 S 167 176 Neil Robertson Paul Seymour Graph minors I Excluding a forest 1983 T 35 vip 1 S 39 61 DOI 10 1016 0095 8956 83 90079 5 Neil Robertson Paul Seymour Graph minors XVI Excluding a non planar graph 2003 T 89 vip 1 S 43 76 DOI 10 1016 S0095 8956 03 00042 X Neil Robertson Paul D Seymour Graph Minors XX Wagner s conjecture 2004 T 92 vip 2 S 325 357 DOI 10 1016 j jctb 2004 08 001 Petra Scheffler Topics in Combinatorics and Graph Theory R Bodendiek R Henn Physica Verlag 1990 S 613 620 Petra Scheffler Fourth Czechoslovakian Symposium on Combinatorics Graphs and Complexity Jaroslav Nesetril Miroslav Fiedler Elsevier 1992 Konstantin Skodinis Springer Verlag 2000 T 1879 S 403 414 Lecture Notes in Computer Science ISBN 978 3 540 41004 1 DOI 10 1007 3 540 45253 2 37 Konstantin Skodinis Construction of linear tree layouts which are optimal with respect to vertex separation in linear time Journal of Algorithms 2003 T 47 vip 1 S 40 59 DOI 10 1016 S0196 6774 02 00225 0 Karol Suchan Ioan Todinca Proc 33rd International Workshop on Graph Theoretic Concepts in Computer Science WG 2007 Springer Verlag 2007 T 4769 S 258 269 Lecture Notes in Computer Science DOI 10 1007 978 3 540 74839 7 25 Matthew Suderman Pathwidth and layered drawings of trees 3 travnya 2003 2004 T 14 vip 3 S 203 225 DOI 10 1142 S0218195904001433 Atsushi Takahashi Shuichi Ueno Yoji Kajitani Minimal acyclic forbidden minors for the family of graphs with bounded path width 1994 T 127 vip 1 3 S 293 304 DOI 10 1016 0012 365X 94 90092 2 F V Fomin Zadachi presledovaniya i poiska na grafah Elektronnaya biblioteka dissertacij 1996