Vägbredd

I grafteorin är en vägupplösning av en graf $G$ , informellt, en representation av $G$ som en "förtjockad" väggraf , och vägbredden för $G$ är ett tal som mäter hur mycket banan förtjockades för att bilda $G$ . Mer formellt är en bannedbrytning en sekvens av delmängder av hörn av $G$ så att ändpunkterna för varje kant visas i en av delmängderna och så att varje vertex uppträder i en sammanhängande undersekvens av delmängderna, och vägbredden är en mindre än storleken på den största uppsättningen i en sådan nedbrytning. Banbredd är också känd som intervalltjocklek (en mindre än den maximala klickstorleken i en intervallsupergraf av $G$ ), vertexseparationsnummer eller nodsökningsnummer .

Banbredd och vägnedbrytningar är nära analoga med trädbredder och trädsönderdelningar . De spelar en nyckelroll i teorin om grafer : de graffamiljer som är stängda under grafer och inte inkluderar alla skogar kan karakteriseras som att de har en begränsad vägbredd, och de "virvlor" som förekommer i den allmänna strukturteorin för minor- slutna graffamiljer har begränsad vägbredd. Banbredd och grafer för begränsad vägbredd har också tillämpningar inom VLSI- design, grafritning och beräkningslingvistik .

Det är NP-svårt att hitta vägbredden för godtyckliga grafer, eller till och med att approximera den exakt. Problemet är dock löst med fasta parametrar : att testa om en graf har vägbredden $k$ kan lösas på en tid som beror linjärt på grafens storlek men superexponentiellt på $k$ . Dessutom, för flera speciella klasser av grafer, såsom träd , kan vägbredden beräknas i polynomtid utan beroende av $k$ . Många problem i grafalgoritmer kan lösas effektivt på grafer med begränsad vägbredd, genom att använda dynamisk programmering på en väguppdelning av grafen. Bannedbrytning kan också användas för att mäta rymdkomplexiteten hos dynamiska programmeringsalgoritmer på grafer av avgränsad trädbredd .

Definition

Ett exempel på graf

G

med banbredd 2 och dess bannedbrytning av bredd 2. Den nedre delen av bilden är samma graf och banuppdelning med färg lagt till för betoning. (Detta exempel är en anpassning av grafen som presenteras i Bodlaender (1994a), kursivering tillagd)

I den första av sin berömda serie av artiklar om grafiska mindreåriga definierar Neil Robertson och Paul Seymour ( 1983 ) en väguppdelning av en graf $G$ som en sekvens av delmängder $X av$ i hörn av $G$ , med två egenskaper:

För varje kant av $G$ finns det ett $i$ så att båda ändpunkterna på kanten tillhör delmängden $Xi,$ och
För vart tredje index $i \leq j \leq k$ , $X_{i}\cap X_{k}\subseteq X_{j}.$

Den andra av dessa två egenskaper är ekvivalent med att kräva att delmängderna som innehåller en viss vertex bildar en sammanhängande delsekvens av hela sekvensen. På språket i de senare artiklarna i Robertson och Seymours graph minor-serie, är en path-decomposition en trädupplösning $(X, T)$ där det underliggande trädet $T$ för nedbrytningen är en path graph .

Bredden på en bannedbrytning definieras på samma sätt som för trädnedbrytningar, som $max i | X i | - 1$ , och vägbredden för $G$ är den minsta bredden av någon vägnedbrytning av $G$ . Subtraktionen av en från storleken på $X i$ i denna definition gör liten skillnad i de flesta tillämpningar av vägbredd, men används för att göra vägbredden på en väggraf lika med ett.

Alternativa karaktäriseringar

Som Bodlaender (1998) beskriver kan vägbredd karakteriseras på många likvärdiga sätt.

Limningssekvenser

En bannedbrytning kan beskrivas som en sekvens av grafer $Gi är$ som limmas ihop genom att identifiera par av hörn från på varandra följande grafer i sekvensen, så att resultatet av att utföra alla dessa limningar $G$ . Graferna $Gi G$ kan tas som de inducerade subgraferna av mängderna $Xi i$ den första definitionen av bannedbrytningar, med två hörn i på varandra följande inducerade subgrafer som limmas ihop när de induceras av samma vertex i $och$ i den andra riktningen man kan återställa uppsättningarna $X i$ som vertexuppsättningarna för graferna $Gi .$ Bredden på bannedbrytningen är då en mindre än det maximala antalet hörn i en av graferna $Gi .$

Intervalltjocklek

En intervallgraf med vägbredd två, en mindre än kardinaliteten för dess fyra maximala klick

ABC

,

ACD

,

CDE

och

CDF

.

Banbredden för varje graf $G$ är lika med en mindre än det minsta klicktalet i en intervallgraf som innehåller $G$ som en subgraf. Det vill säga, för varje bannedbrytning av $G$ kan man hitta en intervallsupergraf av $G$ , och för varje intervallsupergraf av $G$ kan man hitta en bannedbrytning av $G$ , så att sönderdelningens bredd är en mindre än klicknumret för intervallgraf.

I en riktning, anta att en väguppdelning av $G$ ges. Sedan kan man representera sönderdelningens noder som punkter på en linje (i banordning) och representera varje vertex $v$ som ett slutet intervall med dessa punkter som ändpunkter. På detta sätt motsvarar bannedbrytningsnoderna innehållande $v$ de representativa punkterna i intervallet för $v$ . Skärningsgrafen för intervallen som bildas av hörn av $G$ är en intervallgraf som innehåller $G$ som en subgraf . Dess maximala klicker ges av uppsättningarna av intervall som innehåller de representativa punkterna, och dess maximala klickstorlek är ett plus vägbredden för $G$ .

I den andra riktningen, om $G$ är en subgraf till en intervallgraf med klicknummer $p + 1$ , så har $G$ en väguppdelning av bredden $p$ vars noder ges av de maximala klicken i intervallgrafen. Till exempel har intervallgrafen som visas med dess intervallrepresentation i figuren en väguppdelning med fem noder, motsvarande dess fem maximala klicker $ABC$ , $ACD$ , $CDE$ , $CDF$ , och $FG$ ; den maximala klickstorleken är tre och bredden på denna vägnedbrytning är två.

Denna ekvivalens mellan vägbredd och intervalltjocklek är nära analog med ekvivalensen mellan trädbredd och det minsta klicktalet (minus en) för en kordagraf som den givna grafen är en subgraf av. Intervallgrafer är ett specialfall av ackordsgrafer, och ackordsgrafer kan representeras som skärningsdiagram av underträd i ett vanligt träd som generaliserar hur intervallgrafer är skärningsgrafer för undervägar till en bana.

Vertex separationsnummer

Antag att hörnen på en graf $G$ är linjärt ordnade . Då är vertexseparationstalet för $G$ det minsta talet $s$ så att för varje vertex $v$ som mest $s$ hörn är tidigare än $v$ i ordningen men som har $v$ eller en senare vertex som granne. Spetsseparationsnumret för $G$ är det minsta vertexseparationstalet för någon linjär ordning av $G$ . Hönsseparationsnumret definierades av Ellis, Sudborough & Turner (1983) och är lika med vägbredden för $G$ . Detta följer av den tidigare ekvivalensen med klicknummer för intervallgrafer: om $G$ är en subgraf av en intervallgraf $I$ , representerad (som i figuren) på ett sådant sätt att alla intervalländpunkter är distinkta, då är ordningen för de vänstra ändpunkterna i intervaller av $I$ har vertexseparation nummer ett mindre än klicknumret för $I$ . Och i den andra riktningen, från en linjär ordning av $G$ kan man härleda en intervallrepresentation där den vänstra ändpunkten för intervallet för en vertex $v$ är dess position i ordningen och den högra ändpunkten är läget för den granne till $v$ som kommer sist i beställningen.

Nodsökningsnummer

Nodsökningsspelet på en graf är en form av jakt-undvikande där en uppsättning sökare samarbetar för att spåra en flykting som gömmer sig i en graf. Sökarna placeras på hörn av grafen medan flyktingen kan vara i vilken kant som helst av grafen, och flyktingens plats och rörelser är dolda för sökarna. I varje sväng kan några eller alla sökare röra sig (godtyckligt, inte nödvändigtvis längs kanter) från en vertex till en annan, och sedan kan flyktingen röra sig längs vilken bana som helst i grafen som inte passerar genom en sökaren-ockuperad vertex. Flytlingen fångas när båda ändpunkterna på hans kant är ockuperade av sökare. Nodsökningsnumret för en graf är det minsta antal sökare som behövs för att säkerställa att flyktingen kan garanteras fångas, oavsett hur han rör sig. Som Kirousis & Papadimitriou (1985) visar är nodsökningsnumret för en graf lika med dess intervalltjocklek. Den optimala strategin för sökarna är att flytta sökarna så att de i på varandra följande varv bildar de separerande uppsättningarna av en linjär ordning med minimalt vertexseparationsnummer.

Gräns

Ett larvträd , en maximal graf med banbredd en.

Varje $n$ -vertexgraf med banbredd $k$ har högst $k (n - k + (k - 1)/2)$ kanter, och graferna för maximal vägbredd- $k$ (grafer till vilka inga fler kanter kan läggas till utan att öka vägbredden) har exakt så många kanter. En graf med maximal vägbredd $-k$ måste vara antingen en $k$ -bana eller en $k$ -larv, två speciella typer av $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, separerar varje maximal klick grafen i två eller flera komponenter, eller så innehåller den en enda bladvertex, en vertex som bara tillhör en enda 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$ -blad vardera intill en separator $k$ -klick av k $-$ vägen. Speciellt de maximala graferna för vägbredd en är exakt larvträden .

Eftersom bannedbrytningar är ett specialfall av träduppdelningar, är vägbredden för en graf större än eller lika med dess trädbredd . Banbredden är också mindre än eller lika med cutwidth , det minsta antalet kanter som korsar ett snitt mellan lägre numrerade och högre numrerade hörn i ett optimalt linjärt arrangemang av hörn i en graf; detta följer eftersom vertexseparationsnumret, antalet lägre numrerade hörn med högre numrerade grannar, som mest kan vara lika med antalet skurna kanter. Av liknande skäl är skärbredden som mest banbredden gånger den maximala graden av hörn i en given graf.

Alla $n$ -vertexskogar har vägbredd $O (log n)$ . Ty i en skog kan man alltid hitta ett konstant antal hörn vars borttagande $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 2 n⁄ 3 lämnar$ en skog som kan delas upp i två mindre delskogar med högst hörn vardera. Ett linjärt arrangemang som bildas genom att rekursivt dela upp var och en av dessa två delskogar, placera de separerande hörnen mellan dem, har logaritmiskt vertexsökningsnummer. Samma teknik, tillämpad på en trädnedbrytning av en graf, visar att om trädbredden för en $n - (t logn)$ $vertexgraf$ G $är$ t $,$ så är vägbredden för $G$ O . Eftersom ytterplanära grafer , serie-parallella grafer och Halin-grafer alla har en begränsad trädbredd, har de alla också högst logaritmisk vägbredd.

Förutom dess relationer till trädbredd, är vägbredd också relaterad till klickbredd och skärbredd , via linjediagram ; linjediagrammet $L (G)$ i en graf $G$ har en vertex för varje kant av $G$ och två hörn i $L (G)$ ligger intill när de motsvarande två kanterna på $G$ delar en ändpunkt. 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 den disjunkta föreningsoperationen från klickbredd med operationen att angränsa en enda ny vertex. Om en sammankopplad graf med tre eller fler hörn har maximal grad tre, är dess skärbredd lika med vertexseparationsnumret för dess linjegraf.

I vilken plan graf som helst är vägbredden högst proportionell mot kvadratroten av antalet hörn. Ett sätt att hitta en vägnedbrytning med denna bredd är (på samma sätt som den logaritmiska vägnedbrytningen av skogar som beskrivs ovan) att använda planseparatorsatsen för att hitta en uppsättning O ( $\sqrt n) hörn vars$ avlägsnande separerar rita en graf till två subgrafer om högst $2 n ⁄ 3$ hörn vardera, och sammanfoga rekursivt konstruerade banuppdelningar för var och en av dessa två subgrafer. Samma teknik gäller för alla klasser av grafer för vilka en liknande separatorsats gäller. Eftersom, precis som plana grafer, graferna i vilken fast moll-sluten graffamilj som helst har separatorer med storleken $O (\sqrt n)$ , följer det att vägbredden för graferna i någon fast mol-sluten familj återigen är $O (\sqrt n)$ . För vissa klasser av plana grafer måste kurvans bana och dess dubbla grafs bredd ligga inom en konstant faktor av varandra: gränser för denna form är kända för tvåkopplade ytterplanära grafer och för polyedriska grafer. För 2-kopplade plana grafer är vägbredden för den dubbla grafen mindre än vägbredden för linjegrafen. Det förblir öppet om vägbredden för en plan graf och dess dual alltid ligger inom en konstant faktor av varandra i de återstående fallen.

bevisats att vägbredden och trädbredden alltid är lika med varandra: detta är sant för kografer , permutationsgrafer , komplementen till jämförbarhetsgrafer och jämförbarhetsgraferna för intervallordningar .

Olöst problem i matematik :

Vilken är den största möjliga vägbredden för en $n$ -vertex kubisk graf ?

(fler olösta problem i matematik)

I vilken kubisk graf som helst, eller mer allmänt vilken graf som helst med maximal vertexgrad tre, är vägbredden högst $n⁄ 6 n + o(n)$ , där $är$ antalet hörn i grafen. Det finns kubiska grafer med banbredden $0,082 n$ , men det är inte känt hur man minskar detta gap mellan denna nedre gräns och $n ⁄ 6$ övre gräns.

Beräkningsväg-nedbrytningar

Det är NP-komplett att bestämma om vägbredden för en given graf är högst $k$ , när $k$ är en variabel som ges som en del av inmatningen. De mest kända värsta tänkbara tidsgränserna för beräkning av vägbredden för godtyckliga $n$ -vertexgrafer är av formen $O (2 n n c)$ för någon konstant $c$ . Ändå är flera algoritmer kända för att beräkna banuppdelningar mer effektivt när vägbredden är liten, när klassen av inmatningsgrafer är begränsad eller ungefär.

Hanterbarhet med fasta parametrar

Banbredden är traktbar med fasta parametrar : för vilken konstant $k som helst$ är det möjligt att testa om vägbredden är högst $k$ , och om så är fallet att hitta en bannedbrytning av bredden $k$ , i linjär tid. I allmänhet fungerar dessa algoritmer i två faser. I den första fasen används antagandet att grafen har banbredd $k$ för att hitta en väguppdelning eller träduppdelning som inte är optimal, men vars bredd kan avgränsas som en funktion av $k$ . I den andra fasen tillämpas en dynamisk programmeringsalgoritm på denna nedbrytning för att hitta den optimala nedbrytningen. Emellertid är tidsgränserna för kända algoritmer av denna typ exponentiella i $k 2$ , opraktiska med undantag för de minsta värdena på $k$ . För fallet $k = 2$ ges en explicit linjär-tidsalgoritm baserad på en strukturell uppdelning av kurvor för vägbredd-2 av de Fluiter (1997) .

Särskilda klasser av grafer

Bodlaender (1994) undersöker komplexiteten i att beräkna vägbredden på olika specialklasser av grafer. Att bestämma huruvida vägbredden för en graf $G$ är högst $k$ förblir NP-komplett när $G$ är begränsad till grafer med avgränsade grader, plana grafer , plana grafer med begränsad grad, kordagrafer , korda domino, komplementen av jämförbarhetsgrafer och tvådelade avstånd -ärftliga grafer . Det följer omedelbart att det också är NP-komplett för de graffamiljer som innehåller de tvådelade avstånds-ärftliga graferna, inklusive de tvådelade graferna, kordala tvådelade graferna, avståndsärftliga graferna och cirkelgraferna .

Däremot kan vägbredden beräknas i linjär tid för träd och skogar. Den kan också beräknas i polynomtid för grafer med avgränsad trädbredd inklusive serie-parallella grafer , ytterplanära grafer och Halin-grafer , såväl som för delade grafer , för komplement till kordagrafer , för permutationsgrafer , för kografer , för cirkulära- båggrafer , för jämförbarhetsgraferna för intervallordningar, och naturligtvis för själva intervallgraferna , eftersom i så fall vägbredden är bara en mindre än det maximala antalet intervall som täcker någon punkt i en intervallrepresentation av grafen.

Approximationsalgoritmer

Det är NP-svårt att approximera vägbredden för en graf inom en additiv konstant. Det mest kända approximationsförhållandet för en polynomtidsapproximationsalgoritm för vägbredd är $O ((log n) 3/2)$ . För tidigare approximationsalgoritmer för vägbredd, se Bodlaender et al. (1992) och Guha (2000) . För uppskattningar av begränsade klasser av grafer, se Kloks & Bodlaender (1992) .

Graf 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 ta bort hörn. Graph minors har en djup teori där flera viktiga resultat involverar vägbredd.

Exklusive en skog

Om en familj $F$ av grafer är stängd för att ta minderåriga (varje minderårig i en medlem av $F$ är också i $F ), så kan$ $F$ av Robertson-Seymour-satsen karakteriseras som de grafer som inte har någon mindre i $X$ , där $X$ är en ändlig uppsättning förbjudna minderåriga . Till exempel Wagners teorem att de plana graferna är de grafer som varken har 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 sådana resultatet av denna typ var av Robertson & Seymour (1983), och relaterar begränsad vägbredd med förekomsten av en skog i familjen av förbjudna minderåriga . Definiera specifikt en familj $F$ av grafer som har begränsad vägbredd om det finns en konstant $p$ så att varje graf i $F$ har en vägbredd som mest $p$ . Sedan 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 är detta resultat enkelt att bevisa: om $X$ inte inkluderar minst en skog, så har de $X$ -moll-fria graferna inte begränsad vägbredd. För i det här fallet inkluderar de $X$ -moll-fria graferna alla skogar, och i synnerhet inkluderar de de perfekta binära träden . Men ett perfekt binärt träd med $2 k + 1$ nivåer har vägbredd $k$ , så i det här fallet har $X$ -moll-fria-graferna obegränsad vägbredd. I den andra riktningen, om $X$ innehåller en $n$ -vertexskog, så har de $X$ -minor-fria graferna vägbredd som mest $n - 2$ .

Hinder för avgränsad vägbredd

De förbjudna minderåriga för grafer av vägbredd 1.

Egenskapen att ha banbredd som högst $p$ är i sig själv stängd för att ta underåriga: om $G$ har en bannedbrytning med bredd som mest $p$ , så förblir samma bannedbrytning giltig om någon kant tas bort från $G$ , och vilken vertex som helst kan avlägsnas från $G$ och från dess bannedbrytning utan att öka bredden. Sammandragning av en kant kan också åstadkommas utan att öka sönderdelningens bredd, genom att slå samman delbanorna som representerar de två ändpunkterna av den sammandragna kanten. Därför kan kurvorna för vägbredd som mest $p$ karakteriseras av en uppsättning $X p$ av uteslutna minderåriga.

Ä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 vertex och triangeln $K 3$ . Emellertid kan uppsättningen av träd i $X p$ vara exakt karakteriserad: dessa träd är exakt de träd som kan bildas av tre träd i $X p - 1$ genom att koppla en ny rotpunkt med en kant till en godtyckligt vald vertex i var och en av tre mindre träd. Till exempel bildas sjuvertexträdet i $X 1$ på detta sätt från tvåvertexträdet (en enda kant) i $X 0$ . Baserat på denna konstruktion kan antalet förbjudna minderåriga i $X p$ visas vara minst $(p!) 2$ . Den kompletta uppsättningen $X 2$ av förbjudna minderåriga för grafer för vägbredd-2 har beräknats; den innehåller 110 olika grafer.

Strukturteori

Grafstruktursatsen för mindre slutna graffamiljer säger att för varje sådan familj $F$ , kan graferna i $F$ delas upp i klicksummor av grafer som kan bäddas in på ytor av begränsat genus , tillsammans med ett begränsat antal spetsar och virvlar för varje komponent i klicksumman. En apex är en vertex som kan ligga intill vilken annan vertex som helst i sin komponent, medan en virvel är en graf av begränsad vägbredd som är limmad in i en av ytorna på det avgränsade släktets inbäddning av en komponent. Den cykliska ordningen av hörnen runt ytan i vilken en virvel är inbäddad måste vara förenlig med sönderdelningen av virveln, i den meningen att att bryta cykeln för att bilda en linjär ordning måste leda till en ordning med ett begränsat vertexseparationsnummer. Denna teori, där vägbredden är intimt kopplad till godtyckliga mindre slutna graffamiljer, har viktiga algoritmiska tillämpningar.

Ansökningar

VLSI

I VLSI- design studerades problemet med vertexseparation ursprungligen som ett sätt att dela upp kretsar i mindre delsystem, med ett litet antal komponenter på gränsen mellan delsystemen.

Ohtsuki et al. (1979) använder intervalltjocklek för att modellera antalet spår som behövs i en endimensionell layout av en VLSI-krets, bildad av en uppsättning moduler som måste kopplas samman av ett system av nät. I deras modell bildar man en graf där hörnen representerar nät, och där två hörn är förbundna med en kant om deras nät båda ansluter till samma modul; det vill säga, om modulerna och näten tolkas som att de bildar noderna och hyperkanterna av en hypergraf så är grafen som bildas av dem dess linjediagram . En intervallrepresentation av en supergraf av denna linjegraf, tillsammans med en färgning av supergrafen, beskriver ett arrangemang av näten längs ett system av horisontella spår (ett spår per färg) på ett sådant sätt att modulerna kan placeras längs spåren i linjär ordning och anslut till lämpliga nät. Det faktum att intervallgrafer är perfekta grafer innebär att antalet färger som behövs, i ett optimalt arrangemang av denna typ, är detsamma som klicknumret för intervallkompletteringen av nettografen.

Gatematrislayout är en specifik stil av CMOS VLSI-layout för booleska logiska kretsar. I grindmatrislayouter fortplantas signaler längs "linjer" (vertikala linjesegment) medan varje grind i kretsen bildas av en sekvens av anordningsegenskaper som ligger längs ett horisontellt linjesegment. Således måste det horisontella linjesegmentet för varje grind korsa de vertikala segmenten för var och en av linjerna som bildar ingångar eller utgångar för grinden. Som i layouterna av Ohtsuki et al. (1979) , en layout av denna typ som minimerar antalet vertikala spår på vilka linjerna ska arrangeras kan hittas genom att beräkna banbredden för en graf som har linjerna som sina hörn och par av linjer som delar en grind som dess kanter. Samma algoritmiska tillvägagångssätt kan också användas för att modellera vikningsproblem i programmerbara logiska arrayer .

Grafritning

Pathwidth har flera tillämpningar för att rita grafer :

De minimala graferna som har ett givet korsningsnummer har en vägbredd som begränsas av en funktion av deras korsningsnummer.
Antalet parallella linjer på vilka hörn av ett träd kan ritas utan kantkorsningar (under olika naturliga restriktioner för hur intilliggande hörn kan placeras med avseende på sekvensen av linjer) är proportionell mot trädets vägbredd.
En k -korsande h -lagerritning av en graf G är en placering av G: s hörn på h distinkta horisontella linjer, med kanter dirigerade som monotona polygonala banor mellan dessa linjer, på ett sådant sätt att det finns högst k korsningar. Graferna med sådana ritningar har en vägbredd som är begränsad av en funktion av h och k . Därför, när h och k båda är konstanta, är det möjligt i linjär tid att bestämma om en graf har en k -korsande h -skiktsritning.
En graf med n hörn och banbredd p kan bäddas in i ett tredimensionellt rutnät med storleken p × p × n på ett sådant sätt att inga två kanter (representerade som räta linjesegment mellan rutnätspunkter) skär varandra. Sålunda har grafer av begränsad vägbredd inbäddningar av denna typ med linjär volym.

Kompilatordesign

I kompileringen av högnivåprogrammeringsspråk uppstår sökvägsbredd i problemet med att omordna sekvenser av rätlinjekod (det vill säga kod utan kontrollflödesgrenar eller slingor) på ett sådant sätt att alla värden som beräknas i koden kan placeras i maskinregister istället för att behöva spillas in i huvudminnet. I denna applikation representerar man koden som ska kompileras som en riktad acyklisk graf i vilken noderna representerar ingångsvärdena till koden och värdena som beräknas av operationerna i koden. En kant från nod x till nod y i denna DAG representerar det faktum att värdet x är en av ingångarna till operation y . En topologisk ordning av hörnen i denna DAG representerar en giltig omordning av koden, och antalet register som behövs för att utvärdera koden i en given ordning ges av ordningens vertexseparationsnummer.

För vilket fast antal w maskinregister som helst är det möjligt att i linjär tid bestämma huruvida ett stycke rätlinjekod kan omordnas på ett sådant sätt att det kan utvärderas med högst w- register. För, om vertexseparationsnumret för en topologisk ordning högst är w , kan den minsta vertexseparationen mellan alla ordningsföljder inte vara större, så den oriktade grafen som bildas genom att ignorera orienteringarna för DAG som beskrivs ovan måste ha vägbredd som mest w . Det är möjligt att testa om så är fallet, med hjälp av de kända algoritmerna med fasta parametrar för vägbredd, och i så fall hitta en väguppdelning för den oriktade grafen, i linjär tid givet antagandet att w är en konstant . När en vägnedbrytning väl har hittats kan en topologisk ordning av bredd w (om en sådan finns) hittas med hjälp av dynamisk programmering, återigen i linjär tid.

Lingvistik

Kornai & Tuza (1992) beskriver en tillämpning av vägbredd i naturlig språkbehandling . I den här applikationen modelleras meningar som grafer, där hörnen representerar ord och kanterna representerar relationer mellan ord; till exempel om ett adjektiv ändrar ett substantiv i meningen så skulle grafen ha en kant mellan dessa två ord. På grund av den begränsade kapaciteten hos det mänskliga korttidsminnet hävdar Kornai och Tuza att denna graf måste ha begränsad vägbredd (mer specifikt hävdar de, vägbredd högst sex), för annars skulle människor inte kunna analysera tal korrekt.

Exponentiella algoritmer

Många problem i grafalgoritmer kan lösas effektivt på grafer med låg vägbredd, genom att använda dynamisk programmering på en väguppdelning av grafen. Till exempel, om en linjär ordning av hörnen av en n -vertexgraf G ges, med vertexseparationsnummer w , så är det möjligt att hitta den maximala oberoende mängden G i tiden O(2 ^w n ). På grafer över begränsad vägbredd leder detta tillvägagångssätt till algoritmer med fasta parametrar, parametriserade av vägbredden. Sådana resultat återfinns inte ofta i litteraturen eftersom de är subsumerade av liknande algoritmer parametriserade av trädbredden; dock uppstår vägbredd även i trädbreddsbaserade dynamiska programmeringsalgoritmer vid mätning av rymdkomplexiteten hos dessa algoritmer.

Samma dynamiska programmeringsmetod kan också tillämpas på grafer med obegränsad vägbredd, vilket leder till algoritmer som löser oparametriserade grafproblem i exponentiell tid . Att till exempel kombinera denna dynamiska programmeringsmetod med det faktum att kubiska grafer har vägbredd n /6 + o( n ) visar att i en kubisk graf kan den maximala oberoende mängden konstrueras i tiden O(2 ^{n /6 + o( n )} ), snabbare än tidigare kända metoder. Ett liknande tillvägagångssätt leder till förbättrade exponentiella tidsalgoritmer för maximalt snitt och minimalt dominerande setproblem i kubiska grafer, och för flera andra NP-hårda optimeringsproblem.

Se även

Boxicitet , ett annat sätt att mäta komplexiteten hos en godtycklig graf i termer av intervallgrafer
Cutwidth , den minsta möjliga bredden på en linjär ordning av en grafs hörn
Träddjup , ett tal som är avgränsat för en mindre sluten graffamilj om och endast om familjen utesluter en sökväg
Degeneration , ett mått på glesheten hos en graf som högst är lika med dess vägbredd
Grafbandbredd , ett annat NP-komplett optimeringsproblem som involverar linjära layouter av grafer
Strahler nummer , ett mått på komplexiteten hos rotade träd definierade på samma sätt som vägbredden för orotade träd

Anteckningar

Alon, Noga ; Seymour, Paul ; Thomas, Robin (1990), "A separator theorem for graphs with a excluded minor and its applications", Proc. 22:a ACM Symp. on Theory of Computing (STOC 1990) , s. 293–299, doi : 10.1145/100216.100254 , ISBN 0897913612 , S2CID 17521329 .
Amini, Omid; Huc, Florian; Pérennes, Stéphane (2009), "On the path-width of planar graphs", SIAM Journal on Discrete Mathematics , 23 (3): 1311–1316, doi : 10.1137/060670146 .
Arnborg, Stefan (1985), "Effektiva algoritmer för kombinatoriska problem på grafer med begränsad nedbrytbarhet – En undersökning", BIT , 25 (1): 2–23, doi : 10.1007/BF01934985 , S2CID 122263659 .
Arnborg, Stefan; Corneil, Derek G. ; Proskurowski, Andrzej (1987), "Komplexiteten i att hitta inbäddningar i ett $k$ -träd", SIAM Journal on Algebraic and Discrete Methods , 8 (2): 277–284, doi : 10.1137/0608024 .
Aspvall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne (2000), "Minneskrav för tabellberäkningar i partiella k -trädsalgoritmer", Algorithmica , 27 (3): 382–394, doi : 10.1007/s004530010025 , S2CID 9690525 .
Berge, Claude (1967), "Some classes of perfect graphs", Graph Theory and Theoretical Physics , New York: Academic Press, s. 155–165 .
Bienstock, Dan; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1991), "Quickly exclusive a forest", Journal of Combinatorial Theory, Series B , 52 (2): 274–283, doi : 10.1016/0095-8956(91)90068-U .
Björklund, Andreas; Husfeldt, Thore (2008), "Exakta algoritmer för exakt tillfredsställelse och antal perfekta matchningar", Algorithmica , 52 (2): 226–249, doi : 10.1007/s00453-007-9149-8 , S2CID 31769388 .
Bodlaender, Hans L. (1994), "En turistguide genom trädbredden", i Dassow, Jürgen; Kelemenová, Alisa (red.), Developments in Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 november 1992) , Topics in Computer Mathematics, vol. 6, Gordon and Breach, s. 1–20 .
Bodlaender, Hans L. (1994a). "En turistguide genom trädbredden". Acta Cybernetica . 11 : 1–2.
Bodlaender, Hans L. (1996), "A linear-time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing , 25 (6): 1305–1317, doi : 10.1137/S0097539793251219 : 71 hdl 41/70 .
Bodlaender, Hans L. (1998), "A partial k -arboretum of graphs with bounded treewidth", Theoretical Computer Science , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228-4 .
Bodlaender, Hans L. ; Fomin, Fedor V. (2002), "Approximation of pathwidth of outerplanar graphs", Journal of Algorithms , 43 (2): 190–200, doi : 10.1016/S0196-6774(02)00001-9 .
Bodlaender, Hans L. ; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1992), "Approximating treewidth, pathwidth, and minimum elimination tree height", Graph-Theoretic Concepts in Computer Science , Lecture Notes in Computer Science , vol. 570, s. 1–12, doi : 10.1007/3-540-55121-2_1 , hdl : 1874/17927 , ISBN 978-3-540-55121-8 .
Bodlaender, Hans L. ; Gustedt, Jens; Telle, Jan Arne (1998), "Linjärtidsregistertilldelning för ett fast antal register", Proc. 9:e ACM–SIAM-symposiet om diskreta algoritmer (SODA '98) (PDF) , s. 574–583 .
Bodlaender, Hans L. ; Kloks, Ton (1996), "Effektiva och konstruktiva algoritmer för grafernas vägbredd och trädbredd", Journal of Algorithms , 21 (2): 358–402, doi : 10.1006/jagm.1996.0049 , hdl : 15374 .
Bodlaender, Hans L. ; Kloks, Ton; Kratsch, Dieter (1993), "Treewidth and pathwidth of permutation graphs", Proc. 20th International Colloquium on Automata, Languages and Programming (ICALP 1993), Lecture Notes in Computer Science, vol. 700, Springer-Verlag, s. 114–125, doi : 10.1007/3-540-56939-1_66 , hdl : 1874/16657 , ISBN 978-3-540-56939-8 .
Bodlaender, Hans L. ; Möhring, Rolf H. (1990), "The pathwidth and treewidth of cographs", Proc. 2nd Scandinavian Workshop on Algorithm Theory , Lecture Notes in Computer Science, vol. 447, Springer-Verlag, s. 301–309, doi : 10.1007/3-540-52846-6_99 , hdl : 1874/16625 , ISBN 978-3-540-52846-3 .
Cattell, Kevin; Dinneen, Michael J.; Fellows, Michael R. (1996), "A simple linear-time algorithm for finding path-decompositions of small width", Information Processing Letters , 57 (4): 197–203, arXiv : math/9410211 , doi : 10.1016/0020 -0190(95)00190-5 , S2CID 2442557 .
Coudert, David; Huc, Florian; Mazauric, Dorian (2012), "A Distributed Algorithm for Computing the Node Search Number in Trees" (PDF) , Algorithmica , 63 (1): 158–190, doi : 10.1007/s00453-011-9524-3 .
Coudert, David; Huc, Florian; Sereni, Jean-Sébastien (2007), "Pathwidth of outerplanar graphs" (PDF) , Journal of Graph Theory , 55 (1): 27–41, doi : 10.1002/jgt.20218 .
Diestel, Reinhard (1995), "Graph Minors I: a short proof of the path-width theorem", Combinatorics, Probability and Computing , 4 (1): 27–30, doi : 10.1017/S0963548300001450 .
Diestel, Reinhard; Kühn, Daniela (2005), "Graph minor hierarchies", Discrete Applied Mathematics , 145 (2): 167–182, doi : 10.1016/j.dam.2004.01.010 .
Demaine, Erik D. ; Hajiaghayi, MohammadTaghi ; Kawarabayashi, Ken-ichi (2005), "Algorithmic graph minor theory: decomposition, approximation and coloring", Proc. 46:e IEEE Symposium on Foundations of Computer Science (FOCS 2005) , s. 637–646, doi : 10.1109/SFCS.2005.14 , ISBN 0-7695-2468-0 , S2CID 13238254 .
Downey, Rod G. ; Fellows, Michael R. (1999), Parameterized Complexity , Springer-Verlag, ISBN 0-387-94883-X .
Dujmović, V. ; Fellows, MR ; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; Whitesides, S. ; Wood, David R. (2008), "On the parameterized complexity of layered graph drawing", Algorithmica , 52 (2): 267–292, doi : 10.1007/s00453-007-9151-1 , S2CID 2298634 .
Dujmović, Vida ; Morin, Pat ; Wood, David R. (2003), "Pad-width and three-dimensional straight-line grid drawings of graphs" (PDF) , Proc. 10th International Symposium on Graph Drawing (GD 2002) , Lecture Notes in Computer Science, vol. 2528, Springer-Verlag, s. 42–53 .
Ellis, JA; Sudborough, IH; Turner, JS (1983), "Graph separation and search number", Proc. 1983 Allerton Conf. om kommunikation, kontroll och datoranvändning . Som citeras av Monien & Sudborough (1988) .
Ellis, JA; Sudborough, IH; Turner, JS (1994), "The vertex separation and search number of a tree", Information and Computation , 113 (1): 50–79, doi : 10.1006/inco.1994.1064 .
Feige, Uriel ; Hajiaghayi, Mohammadtaghi ; Lee, James R. (2005), "Förbättrade approximationsalgoritmer för hörnavskiljare med minsta vikt", Proc. 37th ACM Symposium on Theory of Computing (STOC 2005) , s. 563–572, doi : 10.1145/1060590.1060674 , ISBN 1581139608 , S2CID 1940978 .
Fellows, Michael R. ; Langston, Michael A. (1989), "On search decision and the efficiency of polynomial-time algorithms", Proc. 21st ACM Symposium on Theory of Computing , s. 501–512, doi : 10.1145/73007.73055 , ISBN 0897913078 , S2CID 1854173 .
Ferreira, Afonso G.; Song, Siang W. (1992), "Acheving optimality for gate matrix layout and PLA-folding: a graph theoretic approach", Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92) , Lecture Notes in Computer Science, vol. 583, Springer-Verlag, s. 139–153, doi : 10.1007/BFb0023825 , hdl : 10068/43314 , ISBN 3-540-55284-7 .
de Fluiter, Babette (1997), Algorithms for Graphs of Small Treewidth (PDF) , Ph.D. avhandling, Utrecht University , ISBN 90-393-1528-0 , arkiverad från originalet (PDF) 2011-07-24 , hämtad 2010-05-06 .
Fomin, Fedor V. (2003), "Pathwidth of planar and line graphs", Graphs and Combinatorics , 19 (1): 91–99, doi : 10.1007/s00373-002-0490-z , S2CID 43123449 .
Fomin, Fedor V.; Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algorithms", Information Processing Letters , 97 (5): 191–196, doi : 10.1016/j.ipl.2005.10.012 .
Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve (2008), "Exakta algoritmer för trädbredd och minsta utfyllnad", SIAM Journal on Computing , 38 (3): 1058–1079, doi : 10.1137/050643350 , hdl : 1956/1151 .
Fomin, Fedor V.; Thilikos, Dimitrios M. (2007), "On self duality of pathwidth in polyhedral graph embeddings", Journal of Graph Theory , 55 (1): 42–54, doi : 10.1002/jgt.20219 .
Garbe, Renate (1995), "Tree-width and path-width of comparability graphs of interval orders", Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94) , Lecture Notes in Computer Science, vol. 903, Springer-Verlag, s. 26–37, doi : 10.1007/3-540-59071-4_35 , ISBN 978-3-540-59071-2 .
Golovach, PA (1993), "The cutwidth of a graph and the vertex separation number of the line graph", Discrete Mathematics and Applications , 3 (5): 517–522, doi : 10.1515/dma.1993.3.5.517 , S2CID 59607 .
Guha, Sudipto (2000), "Nested graph dissection and approximation algorithms", Proc. 41:a IEEE Symposium on Foundations of Computer Science (FOCS 2000), sid. 126, doi : 10.1109/SFCS.2000.892072 , ISBN 0-7695-0850-2 , S2CID 9854056 .
Gurski, Frank; Wanke, Egon (2007), "Line graphs of bounded clique-width", Discrete Mathematics , 307 (22): 2734–2754, doi : 10.1016/j.disc.2007.01.020 .
Gustedt, Jens (1993), "On the pathwidth of chordal graphs", Discrete Applied Mathematics , 45 (3): 233–248, doi : 10.1016/0166-218X(93)90012-D .
Habib, Michel; Möhring, Rolf H. (1994), "Treewidth of cocomparability graphs and a new order-theoretic parameter", Order , 11 (1): 47–60, doi : 10.1007/BF01462229 , S2CID 2648030 .
Hliněny, Petr (2003), "Crossing-number critical graphs have bounded path-width", Journal of Combinatorial Theory, Series B , 88 (2): 347–367, doi : 10.1016/S0095-8956(03)00037-6 .
Kashiwabara, T.; Fujisawa, T. (1979), "NP-fullständigheten av problemet med att hitta en graf med ett minimum-klicknummerintervall som innehåller en given graf som en subgraf", Proc. Internationellt symposium om kretsar och system , s. 657–660 .
Kinnersley, Nancy G. (1992), "The vertex separation number of a graph is equal its path-width", Information Processing Letters , 42 (6): 345–350, doi : 10.1016/0020-0190(92)90234-M .
Kinnersley, Nancy G.; Langston, Michael A. (1994), "Obstruction set isolation for the gate matrix layout problem", Discrete Applied Mathematics , 54 (2–3): 169–213, doi : 10.1016/0166-218X(94)90021-3 .
Kirousis, Lefteris M.; Papadimitriou, Christos H. (1985), "Interval graphs and searching" (PDF) , Discrete Mathematics , 55 (2): 181–184, doi : 10.1016/0012-365X(85)90046-9 , arkiverat från originalet (arkiverat från originalet ) PDF) 2011-07-21 .
Kloks, Ton; Bodlaender, Hans L. (1992), "Approximating treewidth and pathwidth of some classes of perfect graphs", Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92) , Lecture Notes in Computer Science, vol. 650, Springer-Verlag, s. 116–125, doi : 10.1007/3-540-56279-6_64 , hdl : 1874/16672 , ISBN 978-3-540-56279-5 .
Kloks, T.; Bodlaender, H. ; Müller, H.; Kratsch, D. (1993), "Computing treewidth and minimum fill-in: allt du behöver är de minimala separatorerna", Proc. 1st European Symposium on Algorithms (ESA'93) (Lecture Notes in Computer Science), vol. 726, Springer-Verlag, s. 260–271, doi : 10.1007/3-540-57273-2_61 .
Kloks, Ton; Kratsch, Dieter; Müller, H. (1995), "Dominoes", Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94) , Lecture Notes in Computer Science, vol. 903, Springer-Verlag, s. 106–120, doi : 10.1007/3-540-59071-4_41 , ISBN 978-3-540-59071-2 .
Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter (2005), "Algorithms based on the treewidth of sparse graphs", Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), Lecture Notes in Computer Science, vol. 3787, Springer-Verlag, s. 385–396, doi : 10.1007/11604686_34 , ISBN 978-3-540-31000-6 .
Korach, Efraim; Solel, Nir (1993), "Tree-width, path-width, and cutwidth", Discrete Applied Mathematics , 43 (1): 97–101, doi : 10.1016/0166-218X(93)90171-J .
Kornai, András; Tuza, Zsolt (1992), "Narrowness, path-width, and their application in natural language processing", Discrete Applied Mathematics , 36 (1): 87–92, doi : 10.1016/0166-218X(92)90208-R .
Lengauer, Thomas (1981), "Svart-vita småsten och grafseparation", Acta Informatica , 16 (4): 465–475, doi : 10.1007/BF00264496 , S2CID 19415148 .
Lopez, Alexander D.; Law, Hung-Fai S. (1980), "A dense gate matrix layout method for MOS VLSI", IEEE Transactions on Electron Devices , 27 (8): 1671–1675, Bibcode : 1980ITED...27.1671L , doi : 10.10 /T-ED.1980.20086 , S2CID 64469353 , Även i det gemensamma numret, IEEE Journal of Solid-State Circuits 15 (4): 736–740, 1980 .
Miller, George A. (1956), "The Magical Number Seven, Plus or Minus Two" , Psychological Review , 63 (2): 81–97, doi : 10.1037/h0043158 , hdl : 11858/00-001M-0000-002 -4646-B , PMID 13310704 .
Möhring, Rolf H. (1990), "Grafproblem relaterade till grindmatrislayout och PLA-vikning", i Tinhofer, G.; Mayr, E.; Noltemeier, H.; et al. (red.), Computational Graph Theory , Computing Supplementum, vol. 7, Springer-Verlag, s. 17–51, ISBN 3-211-82177-5 .
Monien, B.; Sudborough, IH (1988), "Min cut is NP-complete for edge weighted trees", Theoretical Computer Science , 58 (1–3): 209–229, doi : 10.1016/0304-3975(88)90028-X .
Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979), "One-dimensional logic gate assignment and interval graphs", IEEE Transactions on Circuits and Systems , 26 (9): 675–684, doi : 10.1109/TCS.1979.1084695 .
Peng, Sheng-Lung; Ho, Chin-Wen; Hsu, Tsan-sheng; Ko, Ming-Tat; Tang, Chuan Yi (1998), "En linjär-tidsalgoritm för att konstruera en optimal nodsökningsstrategi för ett träd", Proc. 4:e Int. Konf. Computing and Combinatorics (COCOON'98) , Lecture Notes in Computer Science, vol. 1449, Springer-Verlag, s. 197–205 ^{[ död länk ]} .
Proskurowski, Andrzej; Telle, Jan Arne (1999), "Klasser av grafer med begränsade intervallmodeller" (PDF) , Diskret matematik och teoretisk datavetenskap , 3 : 167–176 .
Robertson, Neil ; Seymour, Paul (1983), "Graph minors. I. Excluding a forest", Journal of Combinatorial Theory, Series B , 35 (1): 39–61, doi : 10.1016/0095-8956(83)90079-5 .
Robertson, Neil ; Seymour, Paul (2003), "Graph minors. XVI. Excluding a non-planar graph", Journal of Combinatorial Theory, Series B , 89 (1): 43–76, doi : 10.1016/S0095-8956(03)00042- X .
Robertson, Neil ; Seymour, Paul D. (2004), "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B , 92 (2): 325–357, doi : 10.1016/j.jctb.2004.08.001 .
Scheffler, Petra (1990), "A linear algorithm for the pathwidth of trees", i Bodendiek, R.; Henn, R. (red.), Topics in Combinatorics and Graph Theory , Physica-Verlag, s. 613–620 .
Scheffler, Petra (1992), "Optimal inbäddning av ett träd i en intervallgraf i linjär tid", i Nešetřil, Jaroslav ; Fiedler, Miroslav (red.), Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity , Elsevier .
Skodinis, Konstantin (2000), "Beräkning av optimala linjära layouter av träd i linjär tid", Proc. 8th European Symposium on Algorithms (ESA 2000) , Lecture Notes in Computer Science, vol. 1879, Springer-Verlag, s. 403–414, doi : 10.1007/3-540-45253-2_37 , ISBN 978-3-540-41004-1 .
Skodinis, Konstantin (2003), "Construction of linear tree-layouts which is optimal with respect to vertex separation in linear time", Journal of Algorithms , 47 (1): 40–59, doi : 10.1016/S0196-6774(02) 00225-0 .
Suchan, Karol; Todinca, Ioan (2007), "Pathwidth of circular-arc graphs", Proc. 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007) , Lecture Notes in Computer Science, vol. 4769, Springer-Verlag, s. 258–269, doi : 10.1007/978-3-540-74839-7_25 .
Suderman, Matthew (2004), "Pathwidth and layered drawings of trees" (PDF) , International Journal of Computational Geometry and Applications , 14 ( 3): 203–225, doi : 10.1142 /S0218195904001433 på originalarkivet (PDF) 2003-05-03 .
Takahashi, Atsushi; Ueno, Shuichi; Kajitani, Yoji (1994), "Minimala acykliska förbjudna minderåriga för familjen av grafer med avgränsad vägbredd", Discrete Mathematics , 127 (1–3): 293–304, doi : 10.1016/0012-365X(94)90092-90092 2 .