Spårbredd

I grafteorin är vägnedbrytningen av en graf G  , informellt, representationen av en graf G som en "förtjockad" väg [1] , och vägbredden för en graf G  är ett tal som mäter hur mycket graf G har varit tjocknat. Mer formellt är en bannedbrytning en sekvens av hörn av en delmängd av grafen G så att ändpunkten för varje kant visas i en av delmängderna och varje vertex tillhör (minst) en av uppsättningarna [2] , och banbredden är en mindre än storleken på den största uppsättningen i en sådan sönderdelning. Banbredden är också känd som intervalltjockleken (en mindre än storleken på den största klicken i intervallsupergrafen på grafen G ), vertexseparationsvärdet eller vertexsökningsnumret [ 3] [4] .

Banbredd och vägnedbrytning är nära analoga med trädbredd och trädnedbrytning . De spelar en nyckelroll i teorin om graph minors  - familjer av grafer som är stängda under graph minors och inte omfattar alla skogar kan karakteriseras som att de har en begränsad vägbredd [2] , och de "virvlar" som uppstår i den allmänna strukturella teorin om familjer av grafer stängda med avseende på minderåriga, har en begränsad vägbredd [5] . Vägbredds- och avgränsade vägbreddsgrafer har tillämpningar inom VLSI- teknik , grafvisualisering och beräkningslingvistik .

Problemet med att hitta vägbredden för godtyckliga grafer är NP-hårt . Dessutom är även problemet med att approximera vägbredden exakt NP-hårt [6] [7] . Detta problem är dock fast-parametriskt lösbart  — att testa om en graf har vägbredden k kan lösas i tid som är linjär i storleken på grafen men superexponentiell i k [8] Dessutom, för vissa speciella klasser av grafer, som t.ex. träd , kan vägbredden beräknas i polynomtid oberoende av k [9] [10] . Många problem inom grafteorin kan effektivt lösas på grafer med begränsad vägbredd genom att använda dynamisk programmering på grafens vägupplösning [11] . Trädsönderdelning kan också användas för att uppskatta kapacitetskomplexiteten för dynamiska programmeringsalgoritmer på grafer med begränsad trädbredd [12] .

Definition

I den första berömda serien av artiklar om grafiska mindreåriga definierade Robertson och Seymour [2] en väguppdelning av en graf G som en sekvens av delmängder X i av hörn av graf G med två egenskaper:

  1. För varje kant G finns i så att båda ändpunkterna på kanten tillhör delmängden Xi
  2. För alla tre index i ≤ j ≤ k , X i ∩ X k ⊆ X j .

Den andra av dessa två egenskaper är ekvivalent med kravet att delmängder som innehåller någon vertex bildar en kontinuerlig undersekvens av hela sekvensen. På språket i Robertson och Seymours senare serier om grafmolor är en bannedbrytning en trädupplösning av ( X , T ) där det underliggande nedbrytningsträdet T är en väg .

Banans sönderdelningsbredd definieras på samma sätt som för trädsönderdelningen, som max i  | X i | − 1, och vägbredden på grafen G är lika med den minsta bredden av alla väguppdelningar av grafen G . Att subtrahera en från storleken på X i i denna definition har liten effekt på de flesta tillämpningar av vägbredd, men gör vägbredden lika med en.

Alternativa beskrivningar

Som Bodlaender [3] skriver kan vägbredd beskrivas på många likvärdiga sätt.

Limma sekvenser

En trädnedbrytning kan beskrivas som en sekvens av grafer G i , som limmas ihop genom att identifiera par av hörn i angränsande grafer av sekvensen, och som ett resultat av denna limning bildas en graf G . Som grafer Gi kan vi ta genererade subgrafer av uppsättningar Xi i den första definitionen av bannedbrytning, med limning av hörn i närliggande genererade subgrafer, om dessa hörn genereras av samma vertex från G . I en annan riktning kan man ta X i som vertexuppsättningarna av graferna G i . Bredden på trädnedbrytningen är då en mindre än det maximala antalet hörn i en av graferna G i [2] .

Intervalltjocklek

Banbredden för varje graf G är en mindre än det minsta klicknumret i intervallgrafen som innehåller G som en subgraf [14] . Det vill säga, för varje trädupplösning av grafen G kan man hitta en intervallsupergraf, och för vilken intervallsupergraf G som helst kan man hitta en trädupplösning av grafen G vars nedbrytningsbredd är en mindre än klicknumret på intervallgrafen .

I en riktning, antag att en trädupplösning av en graf G ges. Då kan man representera sönderdelningens hörn som punkter på linjen (i den ordning som de går in i banan) och representera varje vertex v som ett slutet intervall med dessa punkter som ändpunkter. Låt till exempel ( X 1 , . . . . , X r ) vara en vägupplösning av grafen G , punkter på linjen [1, . . . , r], då representationen av vertex v är intervallet . Då motsvarar trädsönderdelningen av de hörn som innehåller v representationen (d.v.s. ändpunkterna) av intervallet för v . Intervallskärningsgrafen som bildas av G :s hörn är en intervallgraf som innehåller G som en subgraf. Dess maximala klick ges av uppsättningen av intervall som innehåller de representerande punkterna, och deras största klickstorlek är en större än vägbredden på grafen G .

I den andra riktningen, om G är en subgraf till en intervallgraf med klicknummer p  + 1, så har G en trädupplösning av bredden p vars hörn ges av de maximala klicken i intervallgrafen. Till exempel har intervallgrafen som visas med dess intervallrepresentation i figuren en träduppdelning med fem hörn som motsvarar de fem maximala klicken ABC , ACD , CDE , CDF och FG . Storleken på den maximala klicken är tre, och bredden på denna trädnedbrytning är två.

Denna ekvivalens mellan vägbredd och intervalltjocklek är en nära analogi till ekvivalensen mellan trädbredd och minsta klicknummer (minus en) för en kordagraf vars givna graf är en subgraf. Intervallgrafer är ett specialfall av ackordsgrafer, och ackordsgrafer kan representeras som underträdsskärningsgrafer av allmänna träd, vilket generaliserar tillvägagångssättet där intervallgrafer tolkas som vägundervägsskärningsgrafer.

Vertex delat belopp

Antag att topparna i grafen G är linjärt ordnade . Då är storleken på vertexpartitionen för G det minsta talet s så att, för varje vertex v , som mest s hörn föregår v i ordningen som har v eller en av följande hörn i sin närhet. Höntsdelningsvärdet för grafen G är det minsta vertexdelningsvärdet för någon linjär linjär ordningsföljd av grafen G . Spärrpunktsdelningsvärdet introducerades av Ellis, Sudborough och Turner [15] och är lika med vägbredden på grafen G [16] [17] . Detta följer av den tidigare nämnda ekvivalensen av intervallgrafer och klicktal - om G är en subgraf av en intervallgraf I , representerad (som i figuren) på ett sådant sätt att alla ändar av intervallen är olika, då är ordningen på vänstra änden av intervallen för graf I har ett vertexseparationsvärde ett mindre än klicknumren i kolumn I. I den andra riktningen, från en linjär ordning av G , kan man få en intervallrepresentation där den vänstra ändpunkten för intervallet för vertex v är positionen i ordningen, och den högra ändpunkten är positionen för v :s sista granne i beställningen.

Vertex-sökning nummer

Det bästa spelet på en graf är en typ av jakt-undvikande spel där flera förföljare arbetar tillsammans för att spåra en flykting som gömmer sig i en graf. Förföljarna placeras vid grafens hörn, medan flyktingen kan placeras på vilken kant som helst av grafen, hans position och rörelser är inte synliga för förföljarna. Under nästa drag kan några (eller alla) förföljarna röra sig (godtyckligt, inte nödvändigtvis längs kanter) från en vertex till en annan, och flyktingen rör sig sedan längs vilken bana som helst på grafen, men kan inte passera genom de hörn som upptas av förföljare. En flykting fångas när båda ändarna av bågen han befinner sig på är upptagna av förföljare. Hönssökningsnumret för en graf är det minsta antal förföljare som krävs för att garantera att en flykting fångas, oavsett hans beteende. Som Kyrouzis och Panadimitriou [18] visade är vertexsökningsnumret för en graf lika med dess intervalltjocklek. Den optimala strategin för förföljarna är rörelserna där förföljarna successivt bildar separerande uppsättningar av linjär ordning med minsta hörnavstånd.

Gränser

Varje graf med n hörn och banbredd k har högst k ( n − k + ( k − 1)/2)) kanter, och de maximala graferna med banbredd k (grafer till vilka en kant inte kan läggas till utan att öka banan bredd) har precision är antalet kanter. Den maximala grafen med banbredd k måste vara antingen en k -bana eller en k -larv, d.v.s. en av två speciella sorters k -träd. Ett k -träd är en ackordsgraf med exakt n − k maximala klick , var och en innehåller k + 1 hörn. I ett k -träd som inte i sig är en ( k + 1)-klick , delar varje maximal klick antingen upp grafen i två eller flera komponenter eller innehåller en enda bladvertex, en vertex som bara tillhör en maximal klick. En k -bana är ett k -träd med högst två löv, och en k -larv är ett k - träd som kan delas upp i en k -bana och en uppsättning k -löv, var och en intill k-klickavskiljaren av k - vägen . I synnerhet är de maximala graferna för vägbredd ett exakt larvdiagram [19] .

Eftersom bannedbrytningar är specialfall av trädnedbrytningar, är vägbredden för en graf större än eller lika med dess trädbredd . Banbredden är också mindre än eller lika med skärbredden, det minsta antalet kanter som skär ett snitt mellan hörn med ett lägre index och ett högre index i den optimala linjära ordningen av grafens hörn. Detta följer av att storleken på vertexdelningen, antalet hörn med lägre index med grannar med högre index, inte är större än antalet skäreggar [20] [21] . Av samma anledning överstiger inte skärbredden banbredden multiplicerad med den maximala graden av hörn i den givna grafen [22] [23] .

Varje skog med n hörn har en vägbredd på O(log  n ) [24] [25] [26] . För en skog kan man alltid hitta ett konstant antal hörn vars borttagande resulterar i en skog som kan klyvas i två mindre skogar med maximalt 2 n /3 hörn i var och en av dessa skogar. Den linjära ordning som bildas genom att rekursivt tillämpa en sådan partition har ett logaritmiskt söknummer för hörnen. Samma teknik, tillämpad på trädnedbrytning av en graf, visar att om trädbredden för en n -vertexgraf G är t , så är vägbredden för G O( t  log  n ) [27] [28] . Eftersom ytterplanära grafer , parallella seriella grafer och Halin-grafer alla har en begränsad trädbredd, har de alla en maximal logaritmisk vägbredd.

Förutom att vara relaterad till trädbredd, är vägbredd relaterad till klickbredd och skärbredd via linjediagram . En linjegraf L ( G ) i en graf G har en vertex för varje kant av G och två hörn i L ( G ) ligger intill om de motsvarande två kanterna har G -ändpunkter gemensamma. Vilken familj av grafer som helst har avgränsad vägbredd om och endast om dess linjegrafer har avgränsad linjär klickbredd, där linjär klickbredd ersätter föreningsoperationen i definitionen av klickbredd med operationen att fästa en enda ny vertex [29] . Om en sammankopplad graf med tre eller fler hörn har maximal grad 3, är dess skärbredd lika med vertexdelningen av dess linjegraf [30] .

I vilken plan graf som helst är vägbredden i värsta fall proportionell mot kvadratroten av antalet hörn [31] . Ett sätt att hitta en banas sönderdelning med denna bredd är (liknande den log-bredds sönderdelning som beskrivs ovan) att använda planar partitioneringssatsen för att hitta uppsättningen O(√ n ) hörn vars borttagning delar upp grafen i två subgrafer med en maximalt 2 n /3 hörn i vardera, och koppla samman väguppdelningarna konstruerade rekursivt för dessa två subgrafer. Samma teknik gäller för alla klasser av grafer för vilka en liknande partitioneringssats gäller [32] . Eftersom varje familj av grafer som stängs för att ta underåriga, som i fallet med plana grafer, har en delad uppsättning av hörn av storleken O(√ n ) [33] , följer det att vägbredden för grafer i alla fasta familjer som stängs under mindre är igen O(√ n ). För vissa klasser av plana grafer måste kurvans vägbredd och dess dubbla graf ligga i ett intervall vars gränser beror linjärt på värdena – sådana gränser är kända för dubbelkopplade ytterplanära grafer [34] [35] och för polytop grafer [36] [37] . För dubbelkopplade plana grafer är vägbredden för den dubbla grafen mindre än vägbredden för linjegrafen [38] . Det förblir en öppen fråga om vägbredderna för den plana grafen och dess dubbla alltid är i linjära gränser för resten av fallen.

För vissa klasser av grafer har det bevisats att vägbredd och trädbredd alltid är lika med varandra - detta gäller för kografer [39] , permutationsgrafer [40] , komplement till jämförbarhetsgrafer [41] och jämförbarhetsgrafer av intervallordningar [42] .

Olösta problem i matematik : Vad är den maximala vägbredden för en kubisk graf med hörn?

I vilken kubisk graf som helst , eller mer allmänt vilken graf som helst med en maximal vertexgrad på 3, är vägbredden som mest n /6 + o( n ), där n är antalet hörn i grafen. Det finns kubiska grafer med en vägbredd på 0,082 n , men det är inte känt hur man sluter detta gap mellan den nedre gränsen och den övre gränsen n /6 [43] .

Beräkningsvägsuppdelningar

Att bestämma om vägbredden överskrider ett givet värde k för en given graf är NP-komplett om k är en ingång [6] . De mest kända tidsgränserna ( i värsta fall ) för att beräkna vägbredden för en godtycklig graf med n hörn är O(2 n  n c ) för någon konstant c [44] . Vissa vägnedbrytningsalgoritmer är dock kända för att vara mer effektiva om vägbredden är liten, om indatagrafklassen är begränsad eller om vägbredden behöver approximeras.

Fast parametrisk upplösning

Banbredden är fast-parametriskt upplösbar — för vilken konstant k som helst kan man kontrollera om vägbredden överstiger k , och om den inte gör det, hitta en väguppdelning av bredden k i linjär tid [8] . I allmänhet fungerar dessa algoritmer i två steg. Det första steget använder antagandet att grafen har en vägbredd k för att hitta en vägupplösning eller trädupplösning. Denna nedbrytning är inte optimal, men dess bredd kan begränsas av en funktion av k . I det andra steget tillämpas en dynamisk programmeringsalgoritm för att hitta den optimala nedbrytningen. Tidsgränserna för kända algoritmer av denna typ är dock exponentiella i k 2 och har inget praktiskt intresse, förutom kanske för små värden på k [45] . För fallet k  = 2 gav Fleiter en linjär tidsalgoritm baserad på strukturell nedbrytning av grafer med en vägbredd på 2 [46] .

Särskilda klasser av grafer

Bodlaender [9] gav en översikt över komplexiteten i vägbreddsproblem på olika specialklasser av grafer. Att bestämma om vägbredden för en graf G överstiger k förblir ett NP-komplett problem om G tas från grafer med begränsad grad [47] , plana grafer [47] , plana grafer med begränsad grad [47] , kordalgrafer [48] , chordal domino [49] , komplement till jämförbarhetsgrafer [41] och tvådelade avståndsärvda grafer [50] . Detta antyder omedelbart att problemet också är NP-komplett för familjer av grafer som innehåller tvådelade avståndsärvda grafer , inklusive tvådelade grafer, kordala tvådelade grafer, avståndsärvda grafer och cirkulära grafer [50] .

Emellertid kan vägbredden beräknas i linjär tid för träd och skogar [10] . Det är möjligt att beräkna detta värde i polynomtid för grafer med avgränsad trädbredd, som inkluderar parallellsekventiella grafer , ytterplanära grafer och Halin-grafer [8] , såväl som delade grafer [51] [48] , komplement till kordalgrafer [ 52] , permutationsgrafer [40] , kografer [39] , cirkelbågsdiagram [53] , jämförbarhetsdiagram för intervallordning [42] , och naturligtvis själva intervallgraferna , för för dem är vägbredden helt enkelt en mindre än den maximala intervalltäckningen numret på valfri punkt i intervallrepresentationsgrafen.

Approximationsalgoritmer

Ett NP-hårt problem är approximationen av vägbredden för en graf med en additiv konstant [7] . Den mest kända approximationskoefficienten för polynomtidsapproximationsalgoritmer för vägbredd är O((log  n ) 3/2 ) [54] . Tidiga vägbreddsapproximationsalgoritmer kan hittas i Bodlaender, Gilbert, Hafsteinsson, Klox [7] och Gooh [55] . För en uppskattning av begränsade klasser av grafer, se boken av Clox och Bodlaender [51] .

Räkna minderåriga

En moll av en graf G är en annan graf som bildas av G genom att dra ihop kanter, ta bort kanter och hörn. Graph minors har en djup teori där några viktiga resultat använder vägbredd.

Skogsuteslutning

Om familjen F av grafer stängs under operationen att ta minderåriga (vilken som helst minderårig i en medlem av familjen F ingår också i F ), så kan familjen F enligt Robertson–Seymour-satsen karakteriseras som grafer som inte innehålla minderåriga från X , där X är en ändlig uppsättning av förbjudna minderåriga [56] . Till exempel säger Wagners teorem att plana grafer är grafer som varken innehåller den fullständiga grafen K 5 eller den fullständiga tvådelade grafen K 3,3 som mindre. I många fall är egenskaperna hos F och egenskaperna hos X nära besläktade, och det första resultatet av denna typ erhölls av Robertson och Seymour [2] och det relaterar förekomsten av en begränsad vägbredd till närvaron av en skog i familj av förbjudna minderåriga. Mer specifikt definierar vi en familj F av grafer som att ha en begränsad vägbredd om det finns en konstant p så att vilken graf som helst i F har en vägbredd som mest p . Då har en minderårig sluten familj F avgränsad vägbredd om och endast om uppsättningen X av förbjudna minderåriga för F inkluderar minst en skog.

I en riktning kan detta resultat bevisas direkt - nämligen att om X inte innehåller minst en skog, så har X -mollfria grafer ingen begränsad vägbredd. I det här fallet inkluderar X -moll-fria grafer alla skogar, och i synnerhet perfekta binära träd . Men perfekta binära träd med 2k  + 1 nivåer har vägbredd k , så i det här fallet har de X -minor-fria graferna obegränsad vägbredd. I motsatt riktning, om X innehåller en skog med n hörn, så har X -mollfria grafer vägbredd som mest n  − 2 [57] [58] [59] .

Uppskattningar av spårbredd

Egenskapen att ha en banbredd som mest p är i sig själv en minor-closed egenskap - om G har en bannedbrytning med bredd som mest p , förblir samma bannedbrytning sann om någon kant tas bort från G också som vilken som helst en vertex kan tas bort från G och dess bannedbrytning utan att öka bredden. En kantsammandragning kan också fullbordas utan att öka bredden på nedbrytningen genom att slå samman delbanorna som representerar de två ändarna av den kant som dras samman. Sålunda kan grafer med vägbredd som mest p karakteriseras av mängden X p av förbjudna minderåriga [56] [16] [60] [61] .

Även om X p nödvändigtvis inkluderar minst en skog, är det inte sant att alla grafer i X p är skogar. Till exempel består X 1 av två grafer, ett träd med sju hörn och en triangel K 3 . Uppsättningen av träd i X p kan dock beskrivas exakt - det är exakt de träd som kan bildas av tre träd från X p  − 1 genom att bilda en ny rot och koppla den med kanter till godtyckligt valda hörn av mindre träd. Till exempel bildas ett träd med sju hörn i X 1 av träd med två hörn (en kant) från X 0 . Baserat på denna konstruktion kan det visas att antalet förbjudna minderåriga i X p inte är mindre än ( p !) 2 [16] [60] [61] . Den kompletta uppsättningen X 2 av förbjudna minderåriga för grafer med vägbredd 2 har beräknats. Denna uppsättning innehåller 110 olika grafer [62] .

Strukturteori

Grafstruktursatsen för familjer av mindre slutna grafer säger att för varje familj F där grafer kan delas upp i klicksummor, grafer som kan bäddas in i ytor av begränsat släkte , tillsammans med ett begränsat antal hörn och virvlar, för varje del av klicksumman . En vertex är en vertex som ligger intill komponentens alla hörn, och en virvel är en graf av avgränsad vägbredd som är limmad på komponentens yta med en injektion av avgränsat släkte. Den cykliska ordningen av hörnen runt ytan där virveln är kapslad måste vara förenlig med trädnedbrytningen av virveln i den meningen att bryta cykeln för att bilda en linjär ordning måste resultera i en ordning med en begränsad mängd vertexseparation [ 5] . Denna teori, där vägbredden är nära relaterad till godtyckliga familjer av grafer stängda under mindreåriga, har en viktig algoritmisk tillämpning [63] .

Applikationer

VLSI

Under utvecklingen av VLSI studerades problemet med att dela hörn ursprungligen som ett sätt att dela upp kedjor i mindre delsystem med ett litet antal komponenter vid gränsen mellan systemen [47] .

Otsuki, Mori, Kuh och Kashiwabara [64] använde intervalltjocklek för att modellera antalet ledare som behövs i ett endimensionellt arrangemang av VLSI-kretsar som bildas av flera moduler som ska anslutas av ett nätverkssystem. I deras modell kan man bilda en graf där hörnen representerar kedjor och där två hörn är förbundna med en kant om deras kedjor är kopplade till samma modul. Det vill säga, om moduler och kedjor förstås som hörn och hyperkanter av en hypergraf , då är grafen som bildas av dem ett linjediagram av en hypergraf . Supergrafintervallrepresentationen av denna linjegraf, tillsammans med färgningen av supergrafen, beskriver arrangemanget av nät längs horisontella spår (ett spår för varje färg), så att moduler kan arrangeras längs spåren i linjär ordning och kopplas till önskade nät. Av det faktum att intervallgrafer är perfekta [65] följer att antalet färger som krävs för en optimal layout av denna typ är lika med klicknumret för kedjegrafens intervallkomplement.

Switchmatrisstapling [66] är en specifik typ av CMOS VLSI-stapling för logiska algebrakretsar . Vid matrisstapling av omkopplare fortplantar sig signalen längs "linjer" (vertikala segment), medan varje omkopplare bildas av en sekvens av element placerade på ett horisontellt segment. Således måste de horisontella segmenten för varje omkopplare skära de vertikala segmenten för varje linje som tjänar som ingång eller utgång för omkopplaren. Liksom i Otsuki, Mori, Kuha och Kashiwabara staplingar [64] kan denna typ av stapling, som minimerar antalet vertikala linjer, beräknas genom att beräkna banbredden för en graf som har linjer som hörn och ett par linjer som hör till en strömbrytare som kanter [67] . Samma algoritmiska tillvägagångssätt kan också användas för att modellera staplingsproblem i programmerbara logiska integrerade kretsar [68] [69] .

Grafvisualisering

Pathwidth har flera grafvisualiseringsapplikationer :

Kompilatordesign

Vid översättning av programmeringsspråk på hög nivå uppstår sökväg i problemet med att omordna linjär kod (det vill säga kod utan kontrolllogik - övergångar och slingor) på ett sådant sätt att alla värden som beräknas i koden kan finnas i maskinregister , och inte tvingas ut i huvudminnet. I den här applikationen representeras den översatta koden som en riktad acyklisk graf (DAG), där hörnen representerar ingångsvärdena för koden och de värden som beräknas som ett resultat av operationer inom koden. En kant från nod x till nod y i denna NAG representerar det faktum att värdet x är en av ingångarna till operationen y . Den topologiska sorteringen av hörnen i denna NAG representerar den korrekta sorteringen av koden, och antalet register som behövs för att exekvera koden i den ordningen ges av ordningens vertexdelning [74] .

För vilket fast antal w register som helst i en maskin kan det bestämmas i linjär tid huruvida en bit linjär kod kan omordnas så att koden som mest kräver w register. Om vertexseparationen för en topologisk ordning är högst w , kan den minsta vertexseparationen bland alla ordningsföljder inte vara större, så oriktade grafer som bildas genom att ignorera orienteringen av NAG som beskrivs ovan måste ha en vägbredd som mest w . Man kan kontrollera om detta är sant med hjälp av kända algoritmer för avgörbara vägbredder med fasta parametrar, och om det är sant, hitta en väguppdelning för oriktade grafer i linjär tid, förutsatt att w är en konstant. När trädsönderdelningen har hittats kan den topologiska ordningen med bredd w (om sådan finns) hittas med hjälp av dynamisk programmering, återigen i linjär tid [74] .

Språkvetenskap

Karnai och Tutsa [75] beskrev tillämpningen av sökvägsbredd på naturlig språkbehandling . I den här applikationen modelleras meningar som grafer där hörn representerar ord och kanter representerar relationer mellan ord. Till exempel, om ett adjektiv ändrar ett substantiv, har grafen en kant mellan de två orden. På grund av den begränsade kapaciteten hos mänskligt korttidsminne hävdar Miller [76] , Kornai och Tutsa att denna graf måste ha en begränsad vägbredd (mer specifikt hävdar de att denna vägbredd inte överstiger sex), annars skulle människor inte kunna att känna igen tal korrekt.

Exponentiella algoritmer

Många problem med grafteorin kan effektivt lösas på grafer med liten vägbredd med hjälp av dynamisk programmering , baserat på grafens sönderdelning [11] . Till exempel, om den linjära ordningen av hörnen i en graf G med n hörn är given och värdet för hörnseparationen är lika med w , då är det möjligt att hitta den största oberoende uppsättningen av grafen G i O(2 w n ) tid [43] . På en graf med begränsad vägbredd leder detta tillvägagångssätt till fast-parametriskt avgörbara vägbreddsparameteriserade algoritmer [67] . Sådana resultat återfinns inte ofta i litteraturen, eftersom de tillhör en grupp liknande trädbreddsparameteriserade algoritmer. Emellertid visas vägbredd även i trädbreddsbaserade dynamiska programmeringsalgoritmer när man mäter kapacitetskomplexiteten för dessa algoritmer [12] .

Samma dynamiska programmeringsteknik kan tillämpas på grafer med obegränsad vägbredd, vilket leder till algoritmer som löser icke-parameteriserade problem på grafer i exponentiell tid . Till exempel, att kombinera den dynamiska programmeringsmetoden med det faktum att kubiska grafer har en vägbredd på n /6 + o( n ) visar att för kubiska grafer kan den maximala oberoende uppsättningen byggas in i O(2 n /6 + o( n ) ) tid, vilket är snabbare än tidigare kända metoder [43] . Ett liknande tillvägagångssätt leder till förbättrade exponentiella tidsalgoritmer för maximalt snitt och minsta dominerande setproblem för kubiska grafer [43] och för vissa andra NP-hårda optimeringsproblem [77] [78] .

Se även

Anteckningar

  1. ↑ Diestel, Kühn, 2005 .
  2. ↑ 1 2 3 4 5 Robertson, Seymour, 1983 .
  3. ↑ 1 2 Bodlaender, 1998 .
  4. ↑ Många av termerna som används i artikeln finns i inledningen till avhandlingen av 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 , sid. 1–2.
  14. ↑ Bodlaender, 1998 , sid. 13, sats 29.
  15. ↑ Ellis, Sudborough, Turner, 1983 .
  16. ↑ 1 2 3 Kinnersley, 1992 .
  17. ↑ Bodlaender, 1998 , sid. Sats 51.
  18. ↑ Kirousis, Papadimitriou, 1985 .
  19. ↑ Proskurowski, Telle, 1999 .
  20. ↑ Korach, Solel, 1993 , sid. 99, Lemma 3.
  21. ↑ Bodlaender, 1998 , sid. 24, sats 47.
  22. ↑ Korach, Solel, 1993 , sid. 99, Lemma 1.
  23. ↑ Bodlaender, 1998 , sid. 24, sats 49.
  24. ↑ Korach, Solel, 1993 , sid. 99, sats 5.
  25. ↑ Bodlaender, 1998 , sid. 30, sats 66.
  26. ↑ Scheffler (1992 ) ger en starkare gräns på stock 3 (2 n  + 1) stigbredden i en n -vertexskog.
  27. ↑ Korach, Solel, 1993 , sid. 100, sats 6.
  28. ↑ Bodlaender, 1998 , sid. 10, följd 24.
  29. ↑ Gurski, Wanke, 2007 .
  30. ↑ Golovach, 1993 .
  31. ↑ Bodlaender, 1998 , sid. 10, följd 23.
  32. ↑ Bodlaender, 1998 , sid. 9, sats 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 , sid. 12.
  46. ↑ de Fluiter, 1997 .
  47. ↑ 1 2 3 4 Monien, Sudborough, 1988 .
  48. ↑ 12 Gusted , 1993 .
  49. ↑ Kloks, Kratsch, Müller, 1995 . En ackordsdomino är en ackordsgraf där vilken vertex som helst hör till högst två maximala klick
  50. ↑ 1 2 Kloks, Bodlaender, Müller, Kratsch, 1993 .
  51. ↑ 1 2 Kloks, Bodlaender, 1992 .
  52. ↑ Garbe (1995 ) tillskriver detta resultat till Ton Clox avhandling från 1993. Garbes polynomtidsalgoritm för jämförbarhetsgrafer av intervallordningar generaliserar detta resultat, eftersom varje ackordsgraf måste vara en jämförbarhetsgraf av denna typ.
  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 , sid. åtta.
  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 .

Litteratur