Latimea benzii

În teoria graficelor, descompunerea traseului unui grafic G  este, informal, reprezentarea unui grafic G ca o cale „îngroșată” [1] , iar lățimea traseului unui grafic G  este un număr care măsoară cât de mult a fost graficul G. ingrosat. Mai formal, o descompunere a drumului este o succesiune de vârfuri ale unei submulțimi a graficului G astfel încât vârfurile de capăt ale fiecărei muchii apar într-una dintre submulțimi și fiecare vârf aparține (cel puțin) uneia dintre mulțimile [2] , și lățimea căii este cu o mai mică decât dimensiunea celui mai mare set într-o astfel de descompunere. Lățimea căii este cunoscută și ca grosimea intervalului (cu o dimensiune mai mică decât dimensiunea celei mai mari clicuri a supergrafului de interval al graficului G ), valoarea separării vârfurilor sau numărul de căutare a vârfurilor [3] [4] .

Lățimea căii și descompunerea căii sunt strâns analoge cu lățimea și descompunerea arborelui . Ele joacă un rol cheie în teoria grafurilor minore  - familii de grafuri care sunt închise sub graf minori și nu includ toate pădurile pot fi caracterizate ca având o lățime de drum limitată [2] , iar „vârtejurile” care apar în structura generală. Teoria familiilor de grafuri închise cu privire la minori, au o lățime de drum limitată [5] . Graficele de lățime de cale și lățime de cale mărginită au aplicații în inginerie VLSI , vizualizare grafică și lingvistică computațională .

Problema găsirii lățimii de cale a graficelor arbitrare este NP-hard . Mai mult, chiar și problema aproximării exacte a lățimii căii este NP-hard [6] [7] . Cu toate acestea, această problemă este rezolvabilă fix-parametric -  testarea dacă un grafic are lățimea de cale k poate fi rezolvată în timp care este liniar în dimensiunea graficului, dar superexponențial în k [8] În plus, pentru unele clase speciale de grafice, cum ar fi arbori , lățimea de cale poate fi calculată în timp polinomial independent de k [9] [10] . Multe probleme din teoria grafurilor pot fi rezolvate eficient pe grafuri cu o lățime de traseu limitată folosind programarea dinamică pe descompunerea căii a grafului [11] . Descompunerea arborelui poate fi folosită și pentru a estima complexitatea capacității a algoritmilor de programare dinamică pe grafice cu lățime limitată a arborelui [12] .

Definiție

În prima serie faimoasă de lucrări despre grafurile minore, Robertson și Seymour [2] au definit o descompunere a căii a unui graf G ca o succesiune de submulțimi X i de vârfuri ale grafului G cu două proprietăți:

  1. Pentru fiecare muchie G , există i astfel încât ambele capete ale muchiei să aparțină submulțimii X i
  2. Pentru oricare trei indici i ≤ j ≤ k , X i ∩ X k ⊆ X j .

A doua dintre aceste două proprietăți este echivalentă cu cerința ca submulțimile care conțin orice vârf să formeze o subsecvență continuă a întregii secvențe. În limbajul seriei ulterioare a lui Robertson și Seymour despre minorii de graf, o descompunere a căii este o descompunere arborescentă a ( X , T ) în care arborele de descompunere subiacent T este o cale .

Lățimea de descompunere a căii este definită în același mod ca și pentru descompunerea arborelui, ca max i  | X i | − 1, iar lățimea traseului graficului G este egală cu lățimea minimă a tuturor descompunerilor traseului graficului G . Scăderea unuia din dimensiunea lui X i în această definiție are un efect redus asupra majorității aplicațiilor de lățime de cale, dar face ca lățimea de cale să fie egală cu unu.

Descrieri alternative

După cum scrie Bodlaender [3] , lățimea de cale poate fi descrisă în multe moduri echivalente.

Secvențe de lipire

O descompunere arborescentă poate fi descrisă ca o succesiune de grafice G i , care sunt lipite împreună prin identificarea perechilor de vârfuri în graficele adiacente ale secvenței și, ca urmare a acestei lipiri, se formează un grafic G. Ca grafice G i putem lua subgrafe generate de mulțimi X i în prima definiție a descompunerii drumului, cu lipirea vârfurilor în subgrafe generate vecine, dacă aceste vârfuri sunt generate de același vârf din G . În altă direcție, se poate lua X i ca mulțimi de vârfuri ale graficelor G i . Lățimea descompunerii arborelui este atunci cu o mai mică decât numărul maxim de vârfuri dintr-unul din graficele G i [2] .

Grosimea intervalului

Lățimea traseului oricărui grafic G este cu o mai mică decât cel mai mic număr de clică al graficului de intervale care conține G ca subgraf [14] . Adică, pentru orice descompunere arborescentă a graficului G , se poate găsi un supergraf de interval, iar pentru orice supergraf de interval G , se poate găsi o descompunere arborescentă a graficului G a cărui lățime de descompunere este cu o mai mică decât numărul clicei din graficul de interval. .

Într-o direcție, să presupunem că este dată o descompunere arborescentă a unui grafic G. Apoi se pot reprezenta vârfurile descompunerii ca puncte pe linie (în ordinea în care intră pe cale) și se pot reprezenta fiecare vârf v ca un interval închis având aceste puncte ca puncte finale. De exemplu, fie ( X 1 , . . . , X r ) o descompunere a traseului graficului G , puncte de pe dreapta [1, . . . , r], atunci reprezentarea vârfului v este intervalul . Apoi, descompunerea arborescentă a vârfurilor care conțin v corespunde reprezentării (adică punctelor finale) intervalului pentru v . Graficul de intersecție a intervalelor format din vârfurile lui G este un grafic de intervale care conține G ca subgraf. Clicile sale maxime sunt date de setul de intervale care conțin punctele reprezentative, iar dimensiunea lor cea mai mare a clicei este cu o mai mare decât lățimea traseului graficului G .

În cealaltă direcție, dacă G este un subgraf al unui grafic de intervale cu număr de clică p  + 1, atunci G are o descompunere arborescentă de lățime p ale cărei vârfuri sunt date de clicurile maxime ale graficului de intervale. De exemplu, graficul intervalului afișat cu reprezentarea lui interval în figură are o descompunere arborescentă cu cinci vârfuri corespunzătoare celor cinci clicuri maxime ABC , ACD , CDE , CDF și FG . Dimensiunea clicei maxime este de trei, iar lățimea acestei descompunere a copacului este de două.

Această echivalență între lățimea căii și grosimea intervalului este o analogie apropiată cu echivalența dintre lățimea arborelui și numărul minim de clicuri (minus unu) al unui grafic cordal al cărui grafic este un subgraf. Graficele cu intervale sunt un caz special de grafice cu corzi, iar graficele cordale pot fi reprezentate ca grafice de intersecție sub-arbore ale arborilor generali, ceea ce generalizează abordarea în care graficele cu intervale sunt interpretate ca grafice de intersecție a căii subcai.

Suma împărțită la vârf

Să presupunem că vârfurile graficului G sunt ordonate liniar . Atunci mărimea partiției de vârf a lui G este cel mai mic număr s astfel încât, pentru fiecare vârf v , cel mult s vârfuri precedă v în ordinea care au v sau unul dintre următoarele vârfuri în vecinătatea lui. Valoarea de împărțire a nodurilor a graficului G este valoarea minimă a divizării vârfurilor a oricărei ordonări liniare a graficului G. Valoarea împărțirii vârfurilor a fost introdusă de Ellis, Sudborough și Turner [15] și este egală cu lățimea de cale a graficului G [16] [17] . Aceasta rezultă din echivalența menționată anterior a graficelor de interval și a numerelor de clic - dacă G este un subgraf al unui grafic de interval I , reprezentat (ca în figură) în așa fel încât toate capetele intervalelor să fie diferite, atunci ordinea Capetele din stânga ale intervalelor graficului I au o valoare de separare a vârfurilor cu o valoare mai mică decât numerele de clică ale coloanei I. În cealaltă direcție, dintr-o ordonare liniară a lui G , se poate obține o reprezentare a intervalului în care capătul din stânga al intervalului pentru vârful v este poziția în ordonare, iar punctul final din dreapta este poziția ultimului vecin al lui v în comandarea.

Numărul de căutare a vârfurilor

Jocul de căutare de top pe un grafic este un tip de joc de evitare a urmăririi în care mai mulți urmăritori lucrează împreună pentru a găsi un fugar care se ascunde într-un grafic. Următorii sunt plasați la vârfurile graficului, în timp ce fugarul poate fi situat pe orice margine a graficului, locația și mișcările sale nu sunt vizibile pentru urmăritori. În timpul următoarei mișcări, unii (sau toți) urmăritori se pot deplasa (în mod arbitrar, nu neapărat de-a lungul marginilor) de la un vârf la altul, iar fugarul se deplasează apoi pe orice cale de pe grafic, dar nu poate trece prin vârfurile ocupate de urmăritori. Un fugar este prins atunci când ambele capete ale arcului în care se află sunt ocupate de urmăritori. Numărul de căutare a vârfurilor unui grafic este numărul minim de urmăritori necesar pentru a garanta capturarea unui fugar, indiferent de comportamentul acestuia. După cum au arătat Kyrouzis și Panadimitriou [18] , numărul de căutare a vârfurilor unui grafic este egal cu grosimea intervalului său. Strategia optimă pentru urmăritori sunt mișcările în care urmăritorii formează succesiv seturi separatoare de ordonare liniară cu separarea minimă a vârfurilor.

Borduri

Orice grafic cu n vârfuri și lățimea traseului k are cel mult k ( n − k + ( k − 1)/2)) muchii, iar graficele maxime cu lățimea drumului k (grafice la care nu se poate adăuga o muchie fără creșterea drumului lățimea) au precizie este numărul de muchii. Graficul maxim cu lățimea traseului k trebuie să fie fie o cale k , fie o omidă k , adică. unul dintre cele două tipuri speciale de k -arbore. Un k -arbore este un graf cordal cu exact n - k clicuri maxime , fiecare conținând k + 1 vârfuri. Într -un arbore k care nu este el însuși o clică ( k + 1) , fiecare clică maximă fie împarte graficul în două sau mai multe componente, fie conține un singur vârf de frunză, un vârf care aparține doar unei clici maxime. O cale k este un arbore k cu cel mult două frunze, iar o omidă k este un arbore k care poate fi împărțit într-un traseu k și un set de frunze k , fiecare adiacent separatorului k-clică. a drumului k . În special, graficele maxime ale lățimii drumului unu sunt exact grafice caterpillar [19] .

Deoarece descompunerea căii sunt cazuri speciale de descompunere a arborilor, lățimea traseului oricărui grafic este mai mare sau egală cu lățimea arborelui său . Lățimea traseului este, de asemenea, mai mică sau egală cu lățimea de tăiere, numărul minim de muchii care intersectează orice tăietură între vârfuri cu un indice mai mic și un indice mai mare în ordonarea liniară optimă a vârfurilor graficului. Aceasta rezultă din faptul că mărimea diviziunii vârfurilor, numărul de vârfuri cu un indice mai mic cu vecini cu un indice mai mare, nu este mai mare decât numărul de muchii de tăiere [20] [21] . Din același motiv, lățimea tăieturii nu depășește lățimea traseului înmulțită cu gradul maxim de vârfuri din graficul dat [22] [23] .

Orice pădure cu n vârfuri are o lățime de cale de O(log  n ) [24] [25] [26] . Pentru o pădure, se poate găsi întotdeauna un număr constant de vârfuri a căror îndepărtare are ca rezultat o pădure care poate fi împărțită în două păduri mai mici cu maximum 2 n /3 vârfuri în fiecare dintre aceste păduri. Ordinea liniară formată prin aplicarea recursivă a unei astfel de partiții are un număr de căutare logaritmică pentru vârfuri. Aceeași tehnică, aplicată la descompunerea arborelui unui grafic, arată că dacă lățimea arborelui unui grafic n -vertex G este t , atunci lățimea traseului lui G este O( t  log  n ) [27] [28] . Deoarece graficele outerplanare , graficele paralele-seriale și graficele Halin au toate o lățime de arbore mărginită, toate au o lățime de cale logaritmică maximă.

Pe lângă faptul că este legată de lățimea arborelui, lățimea de cale este legată de lățimea de clic și lățimea de tăiere prin intermediul graficelor cu linii . Un grafic de linii L ( G ) al unui grafic G are un vârf pentru fiecare muchie a lui G și două vârfuri din L ( G ) sunt adiacente dacă cele două muchii corespunzătoare au G capete în comun. Orice familie de grafice are o lățime de cale mărginită dacă și numai dacă graficele sale liniare au lățimea clicului liniar mărginit, unde lățimea clicului liniar înlocuiește operația de unire în definiția lățimii clicei cu operația de atașare a unui singur vârf nou [29] . Dacă un graf conectat cu trei sau mai multe vârfuri are gradul maxim 3, lățimea sa tăiată este egală cu împărțirea vârfurilor graficului său cu linii [30] .

În orice graf plan , lățimea căii este, în cel mai rău caz, proporțională cu rădăcina pătrată a numărului de vârfuri [31] . O modalitate de a găsi o descompunere a căii cu această lățime este (similar cu descompunerea căii de log-lățime descrisă mai sus) de a folosi teorema de partiționare plană pentru a găsi mulțimea de vârfuri O(√ n ) a căror eliminare împarte graficul în două subgrafe cu o maxim 2 n /3 vârfuri în fiecare și conectează descompunerea căilor construite recursiv pentru aceste două subgrafe. Aceeași tehnică se aplică oricărei clase de grafice pentru care o teoremă de partiționare similară este valabilă [32] . Deoarece orice familie de grafuri închise sub luarea minorilor, ca în cazul grafurilor plane, are un set de împărțire de vârfuri de dimensiunea O(√ n ) [33] , rezultă că lățimea de cale a grafurilor din orice familie fixă ​​închisă sub minori este din nou O(√ n ). Pentru unele clase de grafice plane, lățimea de cale a graficului și lățimea de cale a graficului său dual trebuie să se afle într-un interval ale cărui limite depind liniar de valori - astfel de limite sunt cunoscute pentru graficele exterioare dublu conectate [34] [35] și pentru politop . grafice [36] [37] . Pentru graficele plane dublu conectate, lățimea de cale a graficului dual este mai mică decât lățimea de cale a graficului de linii [38] . Rămâne o întrebare deschisă dacă lățimile de cale ale grafului plan și dualul său sunt întotdeauna în limite liniare pentru restul cazurilor.

Pentru unele clase de grafice, s-a dovedit că lățimea traseului și lățimea arborelui sunt întotdeauna egale între ele - acest lucru este valabil pentru cografe [39] , grafice de permutare [40] , complemente ale graficelor de comparabilitate [41] și grafice de comparabilitate ale ordinelor de interval [42] .

Probleme nerezolvate în matematică : Care este lățimea maximă a traseului unui grafic cubic cu vârfuri?

În orice grafic cubic sau, mai general, în orice grafic cu un grad maxim de vârf de 3, lățimea traseului este de cel mult n /6 + o( n ), unde n este numărul de vârfuri din grafic. Există grafice cubice cu o lățime de cale de 0,082 n , dar nu se știe cum să se închidă acest decalaj între limita inferioară și limita superioară n /6 [43] .

Calcularea descompunerilor de căi

Determinarea dacă lățimea căii depășește o valoare dată k pentru un grafic dat este NP-complet dacă k este o intrare [6] . Cele mai cunoscute limite de timp ( în cel mai rău caz ) pentru calcularea lățimii de cale a unui graf arbitrar cu n vârfuri sunt O(2 n  n c ) pentru o constantă c [44] . Cu toate acestea, se știe că unii algoritmi de descompunere a căii sunt mai eficienți dacă lățimea căii este mică, dacă clasa graficului de intrare este constrânsă sau dacă lățimea căii trebuie aproximată.

Rezolvabilitate parametrică fixă

Lățimea căii este fixă-parametric rezolvabilă — pentru orice constantă k , se poate verifica dacă lățimea căii depășește k , iar dacă nu, găsiți o descompunere a căii a lățimii k în timp liniar [8] . În general, acești algoritmi funcționează în două etape. Primul pas folosește ipoteza că graficul are o lățime de cale k pentru a găsi o descompunere a căii sau o descompunere a arborelui. Această descompunere nu este optimă, dar lățimea ei poate fi limitată de o funcție de k . În a doua etapă, se aplică un algoritm de programare dinamică pentru a găsi descompunerea optimă. Cu toate acestea, limitele de timp pentru algoritmii cunoscuți de acest tip sunt exponențiale în k 2 și nu prezintă interes practic, cu excepția poate pentru valori mici ale lui k [45] . Pentru cazul k  = 2, Fleiter a dat un algoritm de timp liniar bazat pe descompunerea structurală a graficelor cu o lățime de cale de 2 [46] .

Clase speciale de grafice

Bodlaender [9] a oferit o privire de ansamblu asupra complexității problemelor de lățime de cale pe diferite clase speciale de grafice. Determinarea dacă lățimea de cale a unui graf G depășește k rămâne o problemă NP-completă dacă G este luat din grafice de grad mărginit [47] , grafice plane [47] , grafice plane de grad mărginit [47] , grafice de acorduri [48] , domino cu acorduri [49] , complemente ale graficelor de comparabilitate [41] , și grafice bipartite moștenite la distanță [50] . Acest lucru implică imediat că problema este, de asemenea, NP-completă pentru familiile de grafuri care conțin grafuri bipartite moștenite pe distanță , inclusiv grafuri bipartite, grafuri bipartite cordale, grafuri moștenite pe distanță și grafuri circulare [50] .

Cu toate acestea, lățimea traseului poate fi calculată în timp liniar pentru copaci și păduri [10] . Este posibil să se calculeze această valoare în timp polinomial pentru grafice cu lățimea mărginită a arborelui, care includ grafice paralel-secvențiale , grafice exterioare și grafice Halin [8] , precum și grafice split [51] [48] , complemente ale graficelor cordale [ 52] , grafice de permutare [40] , cografe [39] , grafice cu arc circular [53] , grafice de comparabilitate a ordinului de interval [42] , și, desigur , grafice de interval în sine , deoarece pentru ei lățimea traseului este pur și simplu cu o mai mică decât acoperirea intervalului maxim numărul oricărui punct din graficul de reprezentare a intervalului.

Algoritmi de aproximare

O problemă NP-hard este aproximarea lățimii de cale a unui grafic printr-o constantă aditivă [7] . Cel mai cunoscut coeficient de aproximare al algoritmilor de aproximare a timpului polinomial pentru lățimea căii este O((log  n ) 3/2 ) [54] . Algoritmii timpurii de aproximare a lățimii de cale pot fi găsiți în Bodlaender, Gilbert, Hafsteinsson, Klox [7] și Gooh [55] . Pentru o aproximare a claselor restrânse de grafice, vezi cartea lui Clox și Bodlaender [51] .

Numărați minorii

Un minor al unui graf G este un alt graf format din G prin contractarea muchiilor, ștergerea muchiilor și a vârfurilor. Graficele minore au o teorie profundă în care unele rezultate importante folosesc lățimea de cale.

Excluderea pădurii

Dacă familia F de grafice este închisă sub operațiunea de a lua minori (orice minor al unui membru al familiei F este, de asemenea, conținut în F ), atunci prin teorema Robertson-Seymour, familia F poate fi caracterizată ca grafice care nu conțin minori din X , unde X este un set finit de minori interziși [ 56 ] . De exemplu, teorema lui Wagner afirmă că grafurile plane sunt grafuri care nu conțin nici graful complet K 5 , nici graful complet bipartit K 3,3 ca minore. În multe cazuri, proprietățile lui F și proprietățile lui X sunt strâns legate, iar primul rezultat de acest tip a fost obținut de Robertson și Seymour [2] și leagă existența unei lățimi de drum mărginite de prezența unei păduri în familie de minori interzis. Mai precis, definim o familie F de grafice ca având o lățime de cale mărginită dacă există o constantă p astfel încât orice grafic din F are o lățime de cale cel mult p . Atunci o familie minoră închisă F are o lățime de cale mărginită dacă și numai dacă setul X de minori interziși pentru F include cel puțin o pădure.

Într-o direcție, acest rezultat poate fi demonstrat în mod direct - și anume că, dacă X nu conține cel puțin o pădure, atunci graficele fără X -minor nu au o lățime de cale mărginită. În acest caz, graficele fără X -minor includ toate pădurile și, în special, arborii binari perfecți . Dar arborii binari perfecți cu 2k  + 1 niveluri au lățime de cale k , deci în acest caz graficele fără X -minor au lățime de cale nelimitată. În direcția opusă, dacă X conține o pădure cu n vârfuri, atunci graficele libere de X -minore au o lățime de cale cel mult n  − 2 [57] [58] [59] .

Estimări ale lățimii pistei

Proprietatea de a avea o lățime a drumului de cel mult p este, în sine, o proprietate minoră închisă - dacă G are o descompunere a căii cu lățime de cel mult p , atunci aceeași descompunere a căii rămâne adevărată dacă orice muchie este îndepărtată din G , de asemenea ca orice vârf poate fi îndepărtat din G și descompunerea căii sale fără a crește lățimea. O contracție a muchiei poate fi, de asemenea, finalizată fără a crește lățimea descompunerii prin îmbinarea subtraielor reprezentând cele două capete ale muchiei care se contractă. Astfel, graficele cu lățimea de drum cel mult p pot fi caracterizate prin mulțimea X p de minori interziși [56] [16] [60] [61] .

Deși X p include în mod necesar cel puțin o pădure, nu este adevărat că toate graficele din X p sunt păduri. De exemplu, X 1 constă din două grafice, un arbore cu șapte vârfuri și un triunghi K 3 . Cu toate acestea, setul de copaci din X p poate fi descris exact - aceștia sunt exact copacii care pot fi formați din trei copaci din X p  - 1 prin formarea unei noi rădăcini și conectarea acesteia cu margini la vârfuri alese arbitrar ale copacilor mai mici. De exemplu, un arbore cu șapte vârfuri în X 1 este format din arbori cu două vârfuri (o margine) din X 0 . Pe baza acestei construcții, se poate arăta că numărul minorilor interziși în X p nu este mai mic decât ( p !) 2 [16] [60] [61] . Setul complet X 2 de minori interziși pentru graficele cu lățimea de cale 2 a fost calculat. Acest set conține 110 grafice diferite [62] .

Teoria structurală

Teorema structurii grafice pentru familiile de grafice minore închise afirmă că pentru orice familie F în care graficele pot fi descompuse în sume de clicuri, grafice care pot fi încorporate în suprafețe ale genului mărginit , împreună cu un număr mărginit de vârfuri și vârtejuri, pentru fiecare componentă a sumei clicei . Un vârf este un vârf care este adiacent tuturor vârfurilor componentei, iar un vârtej este un grafic cu lățimea drumului mărginit care este lipit de fața componentei cu o injecție de gen mărginit. Ordinea ciclică a vârfurilor din jurul feței în care este imbricat vârtejul trebuie să fie compatibilă cu descompunerea arborescentă a vârtejului, în sensul că întreruperea ciclului pentru a forma o ordine liniară trebuie să rezulte într-o ordine cu o cantitate limitată de separare a vârfurilor . 5] . Această teorie, în care lățimea de cale este strâns legată de familiile arbitrare de grafuri închise sub minori, are o aplicație algoritmică importantă [63] .

Aplicații

VLSI

În timpul dezvoltării VLSI , problema divizării vârfurilor a fost studiată inițial ca o modalitate de a împărți lanțurile în subsisteme mai mici cu un număr mic de componente la limita dintre sisteme [47] .

Otsuki, Mori, Kuh și Kashiwabara [64] au folosit grosimea intervalului pentru a modela numărul de conductori necesari într-un aranjament unidimensional de circuite VLSI formate din mai multe module care urmează să fie conectate printr-un sistem de rețea. În modelul lor, se poate forma un grafic în care vârfurile reprezintă lanțuri și în care două vârfuri sunt conectate printr-o muchie dacă lanțurile lor sunt conectate la același modul. Adică, dacă modulele și lanțurile sunt înțelese ca vârfuri și hipermuchii ale unui hipergraf , atunci graficul format din ele este un grafic cu linii ale unui hipergraf . Reprezentarea intervalului de supergraf a acestui grafic cu linii, împreună cu colorarea supergrafului, descrie aranjarea rețelelor de-a lungul pistelor orizontale (o pistă pentru fiecare culoare), astfel încât modulele să poată fi aranjate de-a lungul pistelor într-o ordine liniară și conectate la plasele dorite. Din faptul că graficele cu intervale sunt perfecte [65] , rezultă că numărul de culori necesar pentru o dispunere optimă de acest tip este egal cu numărul clicei al complementului de interval al graficului în lanț.

Stacking matrix switch [66] este un tip specific de stivuire CMOS VLSI pentru circuite de algebră logică . În stivuirea matricei de comutatoare, semnalul se propagă de-a lungul „liniilor” (segmente verticale), în timp ce fiecare comutator este format dintr-o succesiune de elemente situate pe un segment orizontal. Astfel, segmentele orizontale pentru fiecare comutator trebuie să intersecteze segmentele verticale pentru fiecare linie care servește ca intrare sau ieșire a comutatorului. Ca și în stivuirea Otsuki, Mori, Kuha și Kashiwabara [64] , acest tip de stivuire, care minimizează numărul de linii verticale, poate fi calculat prin calcularea lățimii de cale a unui grafic care are drepte ca vârfuri și o pereche de linii aparținând un comutator ca muchii [67 ] . Aceeași abordare algoritmică poate fi folosită și pentru modelarea problemelor de stivuire în circuite integrate cu logice programabile [68] [69] .

Vizualizare grafică

Pathwidth are mai multe aplicații de vizualizare grafică :

Design compilator

La traducerea limbajelor de programare de nivel înalt, lățimea de cale apare în problema reordonării codului liniar (adică codul fără logica de control - tranziții și bucle) astfel încât toate valorile calculate în cod să poată fi în registrele mașinii și nu este forțat în memoria principală. În această aplicație, codul tradus este reprezentat ca un graf aciclic direcționat (DAG), în care vârfurile reprezintă valorile de intrare pentru cod și valorile calculate ca urmare a operațiilor din cadrul codului. O muchie de la nodul x la nodul y în acest NAG reprezintă faptul că valoarea x este una dintre intrările operației y . Sortarea topologică a vârfurilor din acest NAG reprezintă sortarea corectă a codului, iar numărul de registre necesare executării codului în acea ordine este dat de împărțirea nodurilor ordonării [74] .

Pentru orice număr fix w de registre dintr-o mașină, se poate determina în timp liniar dacă o bucată de cod liniar poate fi reordonată astfel încât codul să necesite cel mult w registre. Dacă separarea vârfurilor unei ordonări topologice este de cel mult w , separarea minimă a vârfurilor dintre toate ordonările nu poate fi mai mare, astfel încât graficele nedirecționate formate prin ignorarea orientării NAG descrise mai sus trebuie să aibă o lățime de cale de cel mult w . Se poate verifica dacă acest lucru este adevărat utilizând algoritmi cunoscuți de lățime de cale determinabilă cu parametri fixe și, dacă este adevărat, găsiți o descompunere a căii pentru grafice nedirecționate în timp liniar, presupunând că w este o constantă. Odată găsită descompunerea arborelui, ordonarea topologică cu lățimea w (dacă există) poate fi găsită folosind programarea dinamică, din nou în timp liniar [74] .

Lingvistică

Karnai și Tutsa [75] au descris aplicarea lățimii de cale la procesarea limbajului natural . În această aplicație, propozițiile sunt modelate ca grafice în care vârfurile reprezintă cuvinte și marginile reprezintă relații dintre cuvinte. De exemplu, dacă un adjectiv modifică un substantiv, atunci graficul are o margine între cele două cuvinte. Datorită capacității limitate a memoriei umane pe termen scurt, Miller [76] , Kornai și Tutsa susțin că acest grafic trebuie să aibă o lățime de cale limitată (mai precis, ei susțin că această lățime de cale nu depășește șase), altfel oamenii nu ar putea pentru a recunoaște corect vorbirea.

Algoritmi exponențiali

Multe probleme ale teoriei grafurilor pot fi rezolvate eficient pe grafuri cu lățime de cale mică folosind programarea dinamică , bazată pe descompunerea căii a grafului [11] . De exemplu, dacă este dată ordinea liniară a vârfurilor unui grafic G cu n vârfuri și valoarea separării vârfurilor este egală cu w , atunci este posibil să găsim cea mai mare mulțime independentă a graficului G în O(2 w n ) timp [43] . Pe un grafic cu lățimea de cale mărginită, această abordare conduce la algoritmi parametrizați cu lățime de cale fixați-parametric determinabili [67] . Astfel de rezultate nu se găsesc adesea în literatură, deoarece aparțin unui grup de algoritmi similari parametrizați cu lățimea arborelui. Cu toate acestea, lățimea de cale apare chiar și în algoritmii de programare dinamică bazați pe treewidth atunci când se măsoară complexitatea capacității a acestor algoritmi [12] .

Aceeași tehnică de programare dinamică poate fi aplicată graficelor cu lățime de cale nelimitată, ceea ce duce la algoritmi care rezolvă probleme neparametrate pe grafice în timp exponențial . De exemplu, combinarea abordării programării dinamice cu faptul că graficele cubice au o lățime de cale de n /6 + o( n ) arată că pentru graficele cubice se poate construi mulțimea independentă maximă în O(2 n /6 + o( n ) ) timp.care este mai rapid decât metodele cunoscute anterior [43] . O abordare similară conduce la algoritmi de timp exponențial îmbunătățiți pentru problemele de tăiere maximă și de set dominant minim pentru graficele cubice [43] și pentru alte probleme de optimizare NP-hard [77] [78] .

Vezi și

Note

  1. ↑ Diesel, Kühn, 2005 .
  2. ↑ 1 2 3 4 5 Robertson, Seymour, 1983 .
  3. ↑ 1 2 Bodlaender, 1998 .
  4. ↑ Mulți dintre termenii folosiți în articol se găsesc în introducerea în disertația lui F. V. Fomin (( Fomin 1996 ))
  5. ↑ 12 Robertson , Seymour, 2003 .
  6. ↑ 1 2 Kashiwabara, Fujisawa, 1979 ; Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979 ; Lengauer 1981 ; Arnborg, Corneil, Proskurowski, 1987 .
  7. ↑ 1 2 3 Bodlaender, Gilbert, Hafsteinsson, Kloks, 1992 .
  8. ↑ 1 2 3 Bodlaender (1996 ); Bodlaender, Kloks (1996 )
  9. ↑ 1 2 Bodlaender, 1994 .
  10. ↑ 12 Möhring , 1990 ; Scheffler, 1990 ; Ellis, Sudborough, Turner, 1994 ; Coudert, Huc, Mazauric, 1998 ; Peng, Ho, Hsu, Ko, Tang, 1998 ; Skodinis, 2000 ; Skodinis (2003 ).
  11. ↑ 12 Arnborg , 1985 .
  12. ↑ 1 2 Aspvall, Proskurowski, Telle, 2000 .
  13. ↑ Bodlaender, 1994 , p. 1–2.
  14. ↑ Bodlaender, 1998 , p. 13, Teorema 29.
  15. ↑ Ellis, Sudborough, Turner, 1983 .
  16. ↑ 1 2 3 Kinnersley, 1992 .
  17. ↑ Bodlaender, 1998 , p. Teorema 51.
  18. ↑ Kirousis, Papadimitriou, 1985 .
  19. ↑ Proskurowski, Telle, 1999 .
  20. ↑ Korach, Solel, 1993 , p. 99, Lema 3.
  21. ↑ Bodlaender, 1998 , p. 24, Teorema 47.
  22. ↑ Korach, Solel, 1993 , p. 99, Lema 1.
  23. ↑ Bodlaender, 1998 , p. 24, Teorema 49.
  24. ↑ Korach, Solel, 1993 , p. 99, Teorema 5.
  25. ↑ Bodlaender, 1998 , p. 30, Teorema 66.
  26. ↑ Scheffler (1992 ) dă o limită mai puternică asupra  lățimii traseului log 3 (2 n + 1) a unei păduri n -vertex.
  27. ↑ Korach, Solel, 1993 , p. 100, Teorema 6.
  28. ↑ Bodlaender, 1998 , p. 10, corolarul 24.
  29. ↑ Gurski, Wanke, 2007 .
  30. ↑ Golovach, 1993 .
  31. ↑ Bodlaender, 1998 , p. 10, corolarul 23.
  32. ↑ Bodlaender, 1998 , p. 9, Teorema 20.
  33. ↑ Alon, Seymour, Thomas, 1990 .
  34. ↑ Bodlaender, Fomin, 2002 .
  35. ↑ Coudert, Huc, Sereni, 2007 .
  36. ↑ Fomin, Thilikos, 2007 .
  37. ↑ Amini, Huc, Perennes, 2009 .
  38. ↑ Fomin, 2003 .
  39. ↑ 1 2 Bodlaender, Möhring, 1990 .
  40. ↑ 1 2 Bodlaender, Kloks, Kratsch, 1993 .
  41. ↑ 1 2 Habib, Möhring, 1994 .
  42. ↑ 12 Garbe , 1995 .
  43. ↑ 1 2 3 4 Fomin, Høie, 2006 .
  44. ↑ Fomin, Kratsch, Todinca, Villagenger, 2008 .
  45. ↑ Downey, Fellows, 1999 , p. 12.
  46. ↑ de Fluiter, 1997 .
  47. ↑ 1 2 3 4 Monien, Sudborough, 1988 .
  48. ↑ 12 Gusted , 1993 .
  49. ↑ Kloks, Kratsch, Müller, 1995 . Un domino cordal este un grafic cordal în care orice vârf aparține la cel mult două clicuri maxime
  50. ↑ 1 2 Kloks, Bodlaender, Müller, Kratsch, 1993 .
  51. ↑ 1 2 Kloks, Bodlaender, 1992 .
  52. ↑ Garbe (1995 ) atribuie acest rezultat tezelor de disertație ale lui Ton Clox din 1993. Algoritmul de timp polinomial al lui Garbe pentru graficele de comparabilitate ale ordonarilor de intervale generalizeaza acest rezultat, deoarece orice graf cordal trebuie sa fie un graf de comparabilitate de acest tip.
  53. ↑ Suchan, Todinca, 2007 .
  54. ↑ Feige, Hajiaghayi, Lee, 2005 .
  55. ↑ Guha, 2000 .
  56. ↑ 12 Robertson , Seymour, 2004 .
  57. ^ Bienstock , Robertson, Seymour, Thomas, 1991 .
  58. ↑ Diesel, 1995 .
  59. ↑ Cattell, Dinneen, Fellows, 1996 .
  60. ↑ 1 2 Takahashi, Ueno, Kajitani, 1994 .
  61. ↑ 1 2 Bodlaender, 1998 , p. opt.
  62. ↑ Kinnersley, Langston, 1994 .
  63. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2005 .
  64. ↑ 1 2 Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979 .
  65. ↑ Berge, 1967 .
  66. ↑ Lopez, Law, 1980 .
  67. ↑ 12 Fellows , Langston, 1989 .
  68. ↑ Möhring, 1990 .
  69. ↑ Ferreira, Song, 1992 .
  70. ↑ Hlineny, 2003 .
  71. ↑ Suderman, 2004 .
  72. ↑ Dujmović, Fellows, Kitching et al., 2008 .
  73. ↑ Dujmovic, Morin, Wood, 2003 .
  74. ↑ 1 2 Bodlaender, Gustedt, Telle, 1998 .
  75. ↑ Kornai, Tuza, 1992 .
  76. ↑ Miller, 1956 .
  77. ↑ Kneis, Mölle, Richter, Rossmanith, 2005 .
  78. ↑ Björklund, Husfeldt, 2008 .

Literatură