Sporbredde

I grafteori er stinedbrydningen af ​​en graf G  , uformelt, repræsentationen af ​​en graf G som en "fortykket" sti [1] , og stibredden af ​​en graf G  er et tal, der måler, hvor meget graf G har været fortykket. Mere formelt er en stinedbrydning en sekvens af hjørner af en delmængde af grafen G , således at endehjørnerne på hver kant optræder i en af ​​delmængderne, og hvert hjørne tilhører (mindst) et af mængderne [2] , og stibredden er en mindre end størrelsen af ​​det største sæt i en sådan nedbrydning. Stibredden er også kendt som intervaltykkelsen (en mindre end størrelsen af ​​den største klike af intervalsupergrafen på grafen G ), vertexadskillelsesværdien eller vertexsøgningsnummeret [3] [4] .

Stibredde og stinedbrydning er tæt analoge med træbredde og trænedbrydning . De spiller en nøglerolle i teorien om graph minor  - familier af grafer, der er lukket under graph minor og ikke omfatter alle skove kan karakteriseres som havende en begrænset stibredde [2] , og de "hvirvler", der opstår i den generelle strukturelle teori om familier af grafer lukket med hensyn til mindreårige, har en begrænset stibredde [5] . Stibredde- og afgrænsede stibredde-grafer har applikationer i VLSI -teknik , grafvisualisering og computerlingvistik .

Problemet med at finde stibredden af ​​vilkårlige grafer er NP-hårdt . Desuden er selv problemet med at tilnærme vejbredden nøjagtigt NP-hårdt [6] [7] . Dette problem er dog fast-parametrisk løseligt —  at teste om en graf har en stibredde k kan løses i tid, der er lineær i størrelsen af ​​grafen, men supereksponentiel i k [8] For nogle specielle klasser af grafer, som f.eks. træer , kan stibredden beregnes i polynomiel tid uafhængig af k [9] [10] . Mange problemer i grafteori kan effektivt løses på grafer med en begrænset stibredde ved hjælp af dynamisk programmering på grafens stinedbrydning [11] . Trænedbrydning kan også bruges til at estimere kapacitetskompleksiteten af dynamiske programmeringsalgoritmer på grafer med begrænset træbredde [12] .

Definition

I den første berømte serie af artikler om grafiske mindreårige definerede Robertson og Seymour [2] en stinedbrydning af en graf G som en sekvens af delmængder X i af hjørner af graf G med to egenskaber:

  1. For hver kant G er der i , således at begge endepunkter af kanten tilhører delmængden Xi
  2. For alle tre indekser i ≤ j ≤ k , X i ∩ X k ⊆ X j .

Den anden af ​​disse to egenskaber svarer til kravet om, at delmængder, der indeholder et hvilket som helst toppunkt, danner en kontinuerlig undersekvens af hele sekvensen. I sproget i Robertson og Seymours senere serie om grafiske minorer er en stinedbrydning en trænedbrydning af ( X , T ), hvor det underliggende nedbrydningstræ T er en sti .

Stiens dekomponeringsbredde defineres på samme måde som for trænedbrydningen, som max i  | X i | − 1, og banebredden af ​​grafen G er lig med minimumsbredden af ​​alle vejnedbrydninger af grafen G . At trække en fra størrelsen af ​​X i i denne definition har ringe effekt på de fleste anvendelser af stibredde, men gør stibredden lig med en.

Alternative beskrivelser

Som Bodlaender [3] skriver , kan stibredde beskrives på mange tilsvarende måder.

Limning af sekvenser

En trænedbrydning kan beskrives som en sekvens af grafer G i , der limes sammen ved at identificere par af hjørner i tilstødende grafer af sekvensen, og som et resultat af denne limning dannes en graf G . Som grafer G i kan vi tage genererede undergrafer af mængder X i i den første definition af banenedbrydning, med limning af toppunkter i nabogenererede subgrafer, hvis disse toppunkter er genereret af det samme toppunkt fra G . I en anden retning kan man tage X i som toppunktsæt af graferne Gi . Bredden af ​​trænedbrydningen er da en mindre end det maksimale antal hjørner i en af ​​graferne G i [2] .

Intervaltykkelse

Stibredden af ​​enhver graf G er én mindre end det mindste kliknummer på intervalgrafen, der indeholder G som en undergraf [14] . Det vil sige, at for enhver trænedbrydning af grafen G kan man finde en intervalsupergraf, og for enhver intervalsupergraf G kan man finde en trænedbrydning af grafen G , hvis dekomponeringsbredde er én mindre end intervalgrafens kliknummer .

Antag i én retning, at der er givet en trænedbrydning af en graf G. Så kan man repræsentere toppunkterne for dekomponeringen som punkter på linjen (i den rækkefølge, de kommer ind i stien) og repræsentere hvert toppunkt v som et lukket interval med disse punkter som endepunkter. Lad for eksempel ( X 1 , . . . . , X r ) være en banenedbrydning af grafen G , punkter på linjen [1, . . . , r], så er repræsentationen af ​​toppunktet v intervallet . Så svarer trænedbrydningen af ​​hjørnerne indeholdende v til repræsentationen (dvs. endepunkter) af intervallet for v . Intervalskæringsgrafen dannet ud fra hjørnerne af G er en intervalgraf, der indeholder G som en undergraf. Dens maksimale kliker er givet af sættet af intervaller, der indeholder de repræsenterende punkter, og deres største klikstørrelse er én større end kurvens G .

I den anden retning, hvis G er en undergraf af en intervalgraf med kliknummer p  + 1, så har G en trænedbrydning af bredden p , hvis toppunkter er givet af intervalgrafens maksimale klik . For eksempel har intervalgrafen vist med dens intervalrepræsentation i figuren en trænedbrydning med fem hjørner svarende til de fem maksimale kliker ABC , ACD , CDE , CDF og FG . Størrelsen af ​​den maksimale klike er tre, og bredden af ​​denne trænedbrydning er to.

Denne ækvivalens mellem stibredde og intervaltykkelse er en tæt analogi til ækvivalensen mellem træbredde og minimum kliktal (minus en) af en kordegraf, hvoraf den givne graf er en undergraf. Intervalgrafer er et specialtilfælde af akkordgrafer, og akkordgrafer kan repræsenteres som undertræsskæringsgrafer af generelle træer, hvilket generaliserer den tilgang, hvor intervalgrafer fortolkes som stiunderstisskæringsgrafer.

Vertex opdelt beløb

Antag, at toppunkterne på grafen G er lineært ordnet . Så er størrelsen af ​​toppunktspartitionen af ​​G det mindste tal s , således at for hvert toppunkt v højst er s hjørner foran v i rækkefølgen, der har v eller et af følgende hjørner i dets naboskab. Toppunktsdelingsværdien af ​​grafen G er den mindste toppunktsplitværdi af enhver lineær lineær rækkefølge af grafen G . vertex split-værdien blev introduceret af Ellis, Sudborough og Turner [15] og er lig med stibredden af ​​grafen G [16] [17] . Dette følger af den tidligere nævnte ækvivalens af intervalgrafer og kliktal - hvis G er en undergraf af en intervalgraf I , repræsenteret (som i figuren) på en sådan måde, at alle ender af intervallerne er forskellige, så er rækkefølgen af venstre ender af intervallerne for graf I har en toppunktsadskillelsesværdi, der er en mindre end kliknumrene i kolonne I. I den anden retning kan man fra en lineær rækkefølge af G få en intervalrepræsentation, hvor det venstre endepunkt af intervallet for toppunktet v er positionen i rækkefølgen, og det højre endepunkt er positionen af ​​v 's sidste nabo i bestillingen.

Vertex-søgningsnummer

Det bedste spil på en graf er en type forfølgelses-undgåelsesspil , hvor flere forfølgere arbejder sammen om at spore en flygtning, der gemmer sig i en graf. Forfølgerne er placeret i spidserne af grafen, mens flygtningen kan være placeret på enhver kant af grafen, hans placering og bevægelser er ikke synlige for forfølgerne. Under det næste træk kan nogle (eller alle) forfølgerne bevæge sig (vilkårligt, ikke nødvendigvis langs kanter) fra et toppunkt til et andet, og den flygtende bevæger sig derefter langs en hvilken som helst bane på grafen, men kan ikke passere gennem de hjørner, der er optaget af forfølgere. En flygtning bliver fanget, når begge ender af buen, han er på, er besat af forfølgere. Topsøgningsnummeret på en graf er det minimumsantal af forfølgere, der er nødvendigt for at garantere fangst af en flygtning, uanset hans adfærd. Som Kyrouzis og Panadimitriou [18] viste , er vertex-søgningsnummeret på en graf lig med dens intervaltykkelse. Den optimale strategi for forfølgerne er bevægelserne, hvor forfølgerne successivt danner adskillende sæt af lineær rækkefølge med den minimale topadskillelse.

Grænser

Enhver graf med n hjørner og banebredde k har højst k ( n − k + ( k − 1)/2)) kanter, og de maksimale grafer med banebredde k (grafer, hvortil en kant ikke kan tilføjes uden at øge stien bredde) har præcision er antallet af kanter. Den maksimale graf med stibredde k skal enten være en k -sti eller en k -larve, dvs. en af ​​to specielle slags k -træer. Et k - træ er en akkordgraf med præcis n − k maksimale kliker , som hver indeholder k + 1 hjørner. I et k - træ, der ikke i sig selv er en ( k + 1)-klik , opdeler hver maksimal klik enten grafen i to eller flere komponenter eller indeholder et enkelt bladvertex, et toppunkt, der kun hører til én maksimal klike. En k -sti er et k -træ med højst to blade, og en k -larve er et k - træ, der kan opdeles i en k -sti og et sæt k -blade, der hver støder op til k-klikseparatoren af k - stien . Især de maksimale grafer for vejbredde en er nøjagtigt larvegrafer [19] .

Da stinedbrydninger er specielle tilfælde af trænedbrydninger, er stibredden af ​​enhver graf større end eller lig med dens træbredde . Stibredden er også mindre end eller lig med snitbredden, det mindste antal kanter, der skærer ethvert snit mellem hjørner med et lavere indeks og et højere indeks i den optimale lineære rækkefølge af grafens hjørner. Dette følger af, at størrelsen af ​​toppunktets splittelse, antallet af toppunkter med et lavere indeks med naboer med et højere indeks, ikke er større end antallet af skærekanter [20] [21] . Af samme grund overstiger skærebredden ikke banebredden ganget med den maksimale grad af hjørner i den givne graf [22] [23] .

Enhver skov med n toppunkter har en stibredde på O(log  n ) [24] [25] [26] . For en skov kan man altid finde et konstant antal knudepunkter, hvis fjernelse resulterer i en skov, der kan opdeles i to mindre skove med maksimalt 2 n /3 knudepunkter i hver af disse skove. Den lineære rækkefølge, der dannes ved rekursiv anvendelse af en sådan partition, har et logaritmisk søgenummer for hjørnerne. Den samme teknik, anvendt på trænedbrydning af en graf, viser, at hvis træbredden af ​​en n -vertex graf G er t , så er stibredden af ​​G O( t  log  n ) [27] [28] . Fordi ydreplanære grafer , parallel-serielle grafer og Halin-grafer alle har en afgrænset træbredde, har de alle en maksimal logaritmisk stibredde.

Ud over at være relateret til træbredde, er stibredde relateret til klikbredde og snitbredde via linjegrafer . En linjegraf L ( G ) af en graf G har et toppunkt for hver kant af G og to hjørner i L ( G ) støder op til hinanden, hvis de tilsvarende to kanter har G -endepunkter til fælles. Enhver familie af grafer har afgrænset stibredde, hvis og kun hvis dens linjegrafer har afgrænset lineær klikbredde, hvor lineær klikbredde erstatter foreningsoperationen i definitionen af ​​klikbredde med operationen med at fastgøre et enkelt nyt toppunkt [29] . Hvis en forbundet graf med tre eller flere spidser har maksimal grad 3, er dens skærebredde lig med topdelingen af ​​dens linjegraf [30] .

I enhver plan graf er vejbredden i værste fald proportional med kvadratroden af ​​antallet af toppunkter [31] . En måde at finde en banedekomponering med denne bredde på er (svarende til log-bredde banedekomponeringen beskrevet ovenfor) at bruge planar partitioneringssætningen til at finde mængden af ​​O(√ n ) toppunkter, hvis fjernelse opdeler grafen i to undergrafer med en maksimalt 2 n /3 hjørner i hver, og forbinder banedekomponeringerne konstrueret rekursivt for disse to undergrafer. Den samme teknik gælder for enhver klasse af grafer, for hvilke en lignende opdelingssætning gælder [32] . Da enhver familie af grafer, der er lukket for mindreårige, som i tilfældet med plane grafer, har et opdelingssæt af hjørner af størrelsen O(√ n ) [33] , følger det, at stibredden af ​​grafer i enhver fast familie, der er lukket under mindre, er igen O(√ n ). For nogle klasser af plane grafer skal stibredden af ​​grafen og stibredden af ​​dens dobbelte graf ligge i et interval, hvis grænser afhænger lineært af værdierne - sådanne grænser er kendt for dobbeltforbundne ydreplanære grafer [34] [35] og for polytope grafer [36] [37] . For dobbeltforbundne plane grafer er stibredden af ​​den dobbelte graf mindre end stibredden af ​​linjegrafen [38] . Det er fortsat et åbent spørgsmål, om stibredderne af den plane graf og dens dual altid er i lineære grænser for resten af ​​tilfældene.

For nogle klasser af grafer er det blevet bevist, at stibredde og træbredde altid er lig med hinanden - dette gælder for kografer [39] , permutationsgrafer [40] , komplementer til sammenlignelighedsgrafer [41] og sammenlignelighedsgrafer af intervalrækkefølger [42] .

Uløste problemer i matematik : Hvad er den maksimale vejbredde af en kubisk graf med hjørner?

I enhver kubisk graf , eller mere generelt enhver graf med en maksimal toppunktsgrad på 3, er stibredden højst n /6 + o( n ), hvor n er antallet af toppunkter i grafen. Der er kubiske grafer med en banebredde på 0,082 n , men det vides ikke, hvordan man lukker dette mellemrum mellem den nedre grænse og den øvre grænse n /6 [43] .

Beregningsstinedbrydninger

At bestemme, om stibredden overstiger en given værdi k for en given graf, er NP-komplet, hvis k er et input [6] . De bedst kendte tidsgrænser ( i værste tilfælde ) for at beregne stibredden af ​​en vilkårlig graf med n toppunkter er O(2 n  n c ) for en eller anden konstant c [44] . Nogle stinedbrydningsalgoritmer vides dog at være mere effektive, hvis stibredden er lille, hvis inputgrafklassen er begrænset, eller hvis stibredden skal tilnærmes.

Fast-parametrisk opløselighed

Stibredden er fast-parametrisk opløselig — for enhver konstant k kan man kontrollere, om stibredden overstiger k , og hvis den ikke gør det, finde en banedekomponering af bredden k i lineær tid [8] . Generelt fungerer disse algoritmer i to trin. Det første trin bruger antagelsen om, at grafen har en stibredde k til at finde en stinedbrydning eller trænedbrydning. Denne nedbrydning er ikke optimal, men dens bredde kan begrænses af en funktion af k . På andet trin anvendes en dynamisk programmeringsalgoritme for at finde den optimale dekomponering. Tidsgrænserne for kendte algoritmer af denne type er dog eksponentielle i k 2 og har ingen praktisk interesse, undtagen måske for små værdier på k [45] . For tilfældet k  = 2 gav Fleiter en lineær tidsalgoritme baseret på strukturel dekomponering af grafer med en stibredde på 2 [46] .

Særlige klasser af grafer

Bodlaender [9] gav et overblik over kompleksiteten af ​​stibreddeproblemer på forskellige specielle klasser af grafer. At bestemme, om stibredden af ​​en graf G overstiger k , forbliver et NP-komplet problem, hvis G er taget fra grafer af afgrænset grad [47] , plane grafer [47] , plane grafer af afgrænset grad [47] , kordegrafer [48] , akkorddominoer [49] , komplementer til sammenlignelighedsgrafer [41] og bipartite afstandsarvede grafer [50] . Dette indebærer umiddelbart, at problemet også er NP-komplet for familier af grafer, der indeholder bipartite distance-arvede grafer , herunder bipartite grafer, akkordale bipartite grafer, distance-arvede grafer og cirkulære grafer [50] .

Stibredden kan dog beregnes i lineær tid for træer og skove [10] . Det er muligt at beregne denne værdi i polynomisk tid for grafer af afgrænset træbredde, som inkluderer parallel-sekventielle grafer , ydreplanære grafer og Halin-grafer [8] såvel som opdelte grafer [51] [48] , komplementer af akkordgrafer [ 52] , permutationsgrafer [40] , kografer [39] , cirkelbuegrafer [53] , intervalrækkefølge sammenlignelighedsgrafer [42] og selvfølgelig selve intervalgrafer , fordi for dem er stibredden simpelthen en mindre end den maksimale intervaldækning antallet af ethvert punkt i intervalrepræsentationsgrafen.

Approksimationsalgoritmer

Et NP-hårdt problem er tilnærmelsen af ​​stibredden af ​​en graf med en additiv konstant [7] . Den bedst kendte tilnærmelseskoefficient for polynomiske tidstilnærmelsesalgoritmer for stibredde er O((log  n ) 3/2 ) [54] . Tidlige stibredde tilnærmelsesalgoritmer kan findes i Bodlaender, Gilbert, Hafsteinsson, Klox [7] og Gooh [55] . For en tilnærmelse af begrænsede klasser af grafer, se bogen af ​​Clox og Bodlaender [51] .

Tæl mindreårige

En mindre af en graf G er en anden graf dannet ud fra G ved at trække kanter sammen, slette kanter og hjørner. Grafiske mindreårige har en dyb teori, hvor nogle vigtige resultater bruger stibredde.

Skovudelukkelse

Hvis familien F af grafer er lukket under driften af ​​at tage mindreårige (enhver mindreårig af et medlem af familien F er også indeholdt i F ), så kan familie F ifølge Robertson-Seymour-sætningen karakteriseres som grafer, der ikke indeholde mindreårige fra X , hvor X er et endeligt sæt af forbudte mindreårige [56] . For eksempel siger Wagners sætning , at plane grafer er grafer, der hverken indeholder den komplette graf K 5 eller den komplette todelte graf K 3,3 som mindre. I mange tilfælde er egenskaberne af F og egenskaberne af X tæt beslægtede, og det første resultat af denne type blev opnået af Robertson og Seymour [2] og det relaterer eksistensen af ​​en afgrænset stibredde til tilstedeværelsen af ​​en skov i familie af forbudte mindreårige. Mere specifikt definerer vi en familie F af grafer som havende en afgrænset stibredde , hvis der eksisterer en konstant p , således at enhver graf i F højst har stibredde p . Så har en mindreårig lukket familie F afgrænset stibredde, hvis og kun hvis sættet X af forbudte mindreårige for F omfatter mindst én skov.

I én retning kan dette resultat bevises direkte - nemlig at hvis X ikke indeholder mindst én skov, så har X -minor-frie grafer ingen afgrænset stibredde. I dette tilfælde inkluderer X -minor-frie grafer alle skove, og især perfekte binære træer . Men perfekte binære træer med 2k  + 1 niveauer har stibredde k , så i dette tilfælde har de X -minor-frie grafer ubegrænset stibredde. I den modsatte retning, hvis X indeholder en skov med n toppunkter, så har X -molfrie grafer højst banebredde n  − 2 [57] [58] [59] .

Sporbreddeestimater

Egenskaben ved at have en banebredde højst p er i sig selv en minor-lukket egenskab - hvis G har en banenedbrydning med bredde på højst p , så forbliver den samme banenedbrydning sand, hvis en kant fjernes fra G også som et hvilket som helst et toppunkt kan fjernes fra G og dets banenedbrydning uden at øge bredden. En kantkontraktion kan også fuldføres uden at øge bredden af ​​dekomponeringen ved at flette de understier, der repræsenterer de to ender af kanten, der kontraheres. Således kan grafer med stibredde højst p karakteriseres ved sættet X p af forbudte mindreårige [56] [16] [60] [61] .

Selvom X p nødvendigvis omfatter mindst én skov, er det ikke rigtigt, at alle grafer i X p er skove. For eksempel består X 1 af to grafer, et træ med syv hjørner og en trekant K 3 . Træsættet i X p kan dog beskrives nøjagtigt - det er præcis de træer, der kan dannes af tre træer fra X p  − 1 ved at danne en ny rod og forbinde den med kanter til vilkårligt valgte toppunkter af mindre træer. For eksempel er et træ med syv hjørner i X 1 dannet af træer med to spidser (en kant) fra X 0 . Ud fra denne konstruktion kan det påvises, at antallet af forbudte mindreårige i X p ikke er mindre end ( p !) 2 [16] [60] [61] . Det komplette sæt X 2 af forbudte mindreårige for grafer med stibredde 2 er blevet beregnet. Dette sæt indeholder 110 forskellige grafer [62] .

Strukturteori

Grafstruktursætningen for familier af mindre lukkede grafer siger, at for enhver familie F , hvor grafer kan dekomponeres til kliksummer, grafer, der kan indlejres i overflader af afgrænset slægt , sammen med et afgrænset antal hjørner og hvirvler, for hver komponent af kliksummen. Et toppunkt er et toppunkt, der støder op til alle komponentens hjørner, og en hvirvel er en graf af afgrænset banebredde, der er limet til komponentens overflade med en indsprøjtning af afgrænset slægt. Den cykliske rækkefølge af hjørnerne omkring den flade, hvori hvirvelen er indlejret, skal være forenelig med trænedbrydningen af ​​hvirvelen i den forstand, at brydning af cyklussen for at danne en lineær rækkefølge skal resultere i en rækkefølge med en begrænset mængde topadskillelse [ 5] . Denne teori, hvor stibredde er tæt forbundet med vilkårlige familier af grafer lukket under mindreårige, har en vigtig algoritmisk anvendelse [63] .

Ansøgninger

VLSI

Under udviklingen af ​​VLSI blev problemet med at opdele hjørner oprindeligt undersøgt som en måde at opdele kæder i mindre delsystemer med et lille antal komponenter ved grænsen mellem systemerne [47] .

Otsuki, Mori, Kuh og Kashiwabara [64] brugte intervaltykkelse til at modellere antallet af ledere, der er nødvendige i et endimensionelt arrangement af VLSI-kredsløb dannet af flere moduler, der skal forbindes af et netværkssystem. I deres model kan man danne en graf, hvor hjørnerne repræsenterer kæder, og hvor to hjørner er forbundet med en kant, hvis deres kæder er forbundet til det samme modul. Det vil sige, at hvis moduler og kæder forstås som hjørner og hyperkanter af en hypergraf , så er grafen dannet af dem en linjegraf af en hypergraf . Supergrafintervalrepræsentationen af ​​denne linjegraf beskriver sammen med farven af ​​supergrafen opstillingen af ​​net langs vandrette spor (et spor for hver farve), således at moduler kan arrangeres langs sporene i en lineær rækkefølge og forbindes med ønskede net. Af det faktum, at intervalgrafer er perfekte [65] , følger det, at antallet af farver, der kræves for et optimalt layout af denne type, er lig med kliknummeret for intervalkomplementet af kædegrafen.

Switch matrix stabling [66] er en specifik slags CMOS VLSI stabling til logiske algebra kredsløb . Ved matrixstabling af switches forplanter signalet sig langs "linjer" (lodrette segmenter), mens hver switch er dannet af en sekvens af elementer placeret på et vandret segment. De vandrette segmenter for hver kontakt skal således skære de lodrette segmenter for hver linje, der tjener som input eller output for kontakten. Som i Otsuki, Mori, Kuha og Kashiwabara stablinger [64] kan denne type stabling, som minimerer antallet af lodrette linjer, beregnes ved at beregne stibredden af ​​en graf, der har linjer som hjørner og et par linjer, der hører til en kontakt som kanter [67] . Den samme algoritmiske tilgang kan også bruges til at modellere stablingsproblemer i programmerbare logiske integrerede kredsløb [68] [69] .

Grafvisualisering

Pathwidth har flere grafvisualiseringsapplikationer :

Compiler design

Ved oversættelse af programmeringssprog på højt niveau opstår stibredde i problemet med at omorganisere lineær kode (det vil sige kode uden kontrollogik - overgange og sløjfer) på en sådan måde, at alle værdier beregnet i koden kan være i maskinregistre , og ikke tvunget ud i hovedhukommelsen. I denne applikation er den oversatte kode repræsenteret som en rettet acyklisk graf (DAG), hvor hjørnerne repræsenterer inputværdierne for koden og værdierne beregnet som et resultat af operationer i koden. En kant fra node x til node y i denne NAG repræsenterer det faktum, at værdien x er et af inputtene til operationen y . Den topologiske sortering af hjørnerne i denne NAG repræsenterer den korrekte sortering af koden, og antallet af registre, der er nødvendige for at udføre koden i den rækkefølge, er givet af toppunktet for rækkefølgen [74] .

For et hvilket som helst fast antal w registre i en maskine kan det i lineær tid bestemmes, om et stykke lineær kode kan omarrangeres, således at koden højst kræver w registre. Hvis toppunktsadskillelsen af ​​en topologisk rækkefølge højst er w , kan den minimale topadskillelse blandt alle rækkefølgen ikke være større, så urettede grafer dannet ved at ignorere orienteringen af ​​den ovenfor beskrevne NAG må højst have en stibredde w . Man kan kontrollere, om dette er sandt ved hjælp af kendte algoritmer med faste parametre, der kan bestemmes af stibredden, og hvis det er sandt, finde en stinedbrydning for urettede grafer i lineær tid, idet det antages, at w er en konstant. Når først trænedbrydningen er fundet, kan den topologiske rækkefølge med bredde w (hvis sådan findes) findes ved hjælp af dynamisk programmering, igen i lineær tid [74] .

Sprogvidenskab

Karnai og Tutsa [75] beskrev anvendelsen af ​​stibredde til naturlig sprogbehandling . I denne applikation er sætninger modelleret som grafer, hvor hjørner repræsenterer ord og kanter repræsenterer forhold mellem ord. For eksempel, hvis et adjektiv ændrer et substantiv, så har grafen en kant mellem de to ord. På grund af den begrænsede kapacitet af menneskelig korttidshukommelse hævder Miller [76] , Kornai og Tutsa, at denne graf skal have en begrænset stibredde (mere specifikt hævder de, at denne stibredde ikke overstiger seks), ellers ville folk ikke være i stand til at genkende tale korrekt.

Eksponentielle algoritmer

Mange problemer med grafteori kan effektivt løses på grafer med lille stibredde ved hjælp af dynamisk programmering , baseret på kurvens stinedbrydning [11] . For eksempel, hvis den lineære rækkefølge af toppunkterne i en graf G med n toppunkter er givet, og toppunktsadskillelsesværdien er lig w , så er det muligt at finde det største uafhængige sæt af grafen G i O(2 w n ) tid [43] . På en graf med afgrænset stibredde fører denne tilgang til fast-parametrisk afgørlige stibredde-parameteriserede algoritmer [67] . Sådanne resultater findes ikke ofte i litteraturen, da de tilhører en gruppe af lignende træ-bredde-parameteriserede algoritmer. Stibredde vises dog selv i træbredde-baserede dynamiske programmeringsalgoritmer, når man måler kapacitetskompleksiteten af disse algoritmer [12] .

Den samme dynamiske programmeringsteknik kan anvendes på grafer med ubegrænset stibredde, hvilket fører til algoritmer, der løser ikke-parameteriserede problemer på grafer i eksponentiel tid . For eksempel, ved at kombinere den dynamiske programmeringstilgang med det faktum, at kubiske grafer har en stibredde på n /6 + o( n ), viser det, at for kubiske grafer kan det maksimale uafhængige sæt indbygges i O(2 n /6 + o( n ) ) tid, hvilket er hurtigere end tidligere kendte metoder [43] . En lignende tilgang fører til forbedrede eksponentielle tidsalgoritmer for maksimal cut og minimum dominerende sæt problemer for kubiske grafer [43] og for nogle andre NP-hårde optimeringsproblemer [77] [78] .

Se også

Noter

  1. ↑ Diestel, Kühn, 2005 .
  2. ↑ 1 2 3 4 5 Robertson, Seymour, 1983 .
  3. ↑ 1 2 Bodlaender, 1998 .
  4. ↑ Mange af de udtryk, der bruges i artiklen, kan findes i introduktionen til F. V. Fomins afhandling (( 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 , s. 1-2.
  14. ↑ Bodlaender, 1998 , s. 13, sætning 29.
  15. ↑ Ellis, Sudborough, Turner, 1983 .
  16. ↑ 1 2 3 Kinnersley, 1992 .
  17. ↑ Bodlaender, 1998 , s. Sætning 51.
  18. ↑ Kirousis, Papadimitriou, 1985 .
  19. ↑ Proskurowski, Telle, 1999 .
  20. ↑ Korach, Solel, 1993 , s. 99, Lemma 3.
  21. ↑ Bodlaender, 1998 , s. 24, sætning 47.
  22. ↑ Korach, Solel, 1993 , s. 99, Lemma 1.
  23. ↑ Bodlaender, 1998 , s. 24, sætning 49.
  24. ↑ Korach, Solel, 1993 , s. 99, sætning 5.
  25. ↑ Bodlaender, 1998 , s. 30, sætning 66.
  26. ↑ Scheffler (1992 ) giver en stærkere afgrænsning på log 3 (2 n  + 1) stibredden af ​​en n -topskov.
  27. ↑ Korach, Solel, 1993 , s. 100, sætning 6.
  28. ↑ Bodlaender, 1998 , s. 10, konsekvens 24.
  29. ↑ Gurski, Wanke, 2007 .
  30. ↑ Golovach, 1993 .
  31. ↑ Bodlaender, 1998 , s. 10, konsekvens 23.
  32. ↑ Bodlaender, 1998 , s. 9, sætning 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, Villanger, 2008 .
  45. ↑ Downey, Fellows, 1999 , s. 12.
  46. ↑ de Fluiter, 1997 .
  47. ↑ 1 2 3 4 Monien, Sudborough, 1988 .
  48. ↑ 12 Gusted , 1993 .
  49. ↑ Kloks, Kratsch, Müller, 1995 . En akkorddomino er en akkordgraf, hvor ethvert toppunkt hører til højst to maksimale kliker
  50. ↑ 1 2 Kloks, Bodlaender, Müller, Kratsch, 1993 .
  51. ↑ 1 2 Kloks, Bodlaender, 1992 .
  52. ↑ Garbe (1995 ) tilskriver dette resultat Ton Clox' afhandling fra 1993. Garbes polynomielle tidsalgoritme for sammenlignelighedsgrafer af intervalordener generaliserer dette resultat, da enhver akkordgraf skal være en sammenlignelighedsgraf af denne type.
  53. ↑ Suchan, Todinca, 2007 .
  54. ↑ Feige, Hajiaghayi, Lee, 2005 .
  55. ↑ Guha, 2000 .
  56. ↑ 12 Robertson , Seymour, 2004 .
  57. ↑ Bienstock, Robertson, Seymour, Thomas, 1991 .
  58. ↑ Diestel, 1995 .
  59. ↑ Cattell, Dinneen, Fellows, 1996 .
  60. ↑ 1 2 Takahashi, Ueno, Kajitani, 1994 .
  61. ↑ 1 2 Bodlaender, 1998 , s. otte.
  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, Sang, 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 .

Litteratur