Träbredd - Treewidth

I grafteori , den treewidth är en oriktad graf ett heltal som specificerar, informellt, hur långt diagrammet är från att vara en träd . Den minsta trädbredden är 1; graferna med trädbredd 1 är exakt träden och skogen . Graferna med högst 2 bredd är serie -parallella grafer . De maximala graferna med trädbredd exakt k kallas k -träd , och graferna med högst kbred kallas partiella k -träd . Många andra välstuderade graffamiljer har också begränsad trädbredd.

Trebredd kan formellt definieras på flera likvärdiga sätt: storleken på det största hörnet i ett trädets sönderdelning av grafen, storleken på den största klicken i en ackordfyllnad av grafen, den maximala ordningen för en fristad som beskriver en strategi för en förföljelse-undanhållningsspel på grafen, eller den maximala ordningen för en bramble , en samling anslutna subgrafer som alla berör varandra.

Treewidth används vanligen som en parameter i den parametriserade komplexitet analys av grafalgoritmer . Många algoritmer som är NP-hårda för allmänna grafer blir lättare när trädbredden begränsas av en konstant.

Begreppet trädbredd introducerades ursprungligen av Umberto Bertelè och Francesco Brioschi ( 1972 ) under namnet dimension . Den återupptäcktes senare av Rudolf Halin ( 1976 ), baserat på egenskaper som den delar med en annan grafparameter, Hadwiger -numret . Senare återupptäcktes den av Neil Robertson och Paul Seymour ( 1984 ) och har sedan dess studerats av många andra författare.

Definition

En graf med åtta hörn och ett trädets sönderdelning av det på ett träd med sex noder. Varje grafkant ansluter två hörn som är listade tillsammans vid någon trädnod, och varje grafpunkt är listad vid noderna i ett sammanhängande träd i trädet. Varje trädnod listar högst tre hörn, så bredden på denna sönderdelning är två.

Ett trädets sönderdelning av en graf G = ( V , E ) är ett träd, T , med noder X ₁ , ..., X _n , där varje X _i är en delmängd av V , som uppfyller följande egenskaper (termen nod är används för att referera till en toppunkt av T för att undvika förvirring med hörn av G ):

Förbundet av alla uppsättningar X _jag lika V . Det vill säga att varje grafpunkt finns i minst en trädnod.
Om X _i och X _j båda innehåller en vertex v , sedan alla noder X _k av T i (unikt) bana mellan X _i och X _j innehålla v samt. Ekvivalent, trädnoder som innehåller vertex v bilda en ansluten underträd av T .
För varje kant ( v , w ) i grafen finns en delmängd X _i som innehåller både v och w . Det vill säga, hörn är intilliggande i grafen endast när motsvarande subtrees har en nod gemensamt.

Den bredden av ett träd nedbrytning är storleken på den största uppsättningen X _I minus ett. Den treewidth tw ( G ) hos en graf G är den minsta bredden bland alla möjliga trädsönderdelningar av G . I denna definition minskar storleken på den största uppsättningen med en för att göra trädbredden på ett träd lika med en.

På motsvarande sätt är trebredden för G en mindre än storleken på den största klicken i ackordgrafen som innehåller G med det minsta klicknumret . En ackordgraf med denna klickstorlek kan erhållas genom att lägga till G en kant mellan varannan hörn som båda tillhör minst en av uppsättningarna X _i .

Trebredd kan också kännetecknas av tillflyktsort , funktioner som beskriver en undanhållningsstrategi för ett visst förföljelse-undanhållningsspel definierat på en graf. En graf G har trebredd k om och endast om den har en oas av ordning k + 1 men av ingen högre ordning, där en tillflyktsort för ordning k + 1 är en funktion β som kartlägger varje uppsättning X med högst k hörn i G till en av de anslutna komponenterna av G \ X och att lyder monotonitet egenskapen att β ( Y ) ⊆ β ( X ) när X ⊆ Y .

Ett bramble av ordning fyra i ett 3 × 3 rutnät, vars existens visar att grafen har trebredd minst 3

En liknande karakterisering kan också göras med hjälp av brambles , familjer av anslutna subgrafer som alla berör varandra (vilket betyder att de delar en topp eller är anslutna med en kant). Ordningen för en bramble är den minsta träffsatsen för familjen av undergrafer, och trädbredden på en graf är en mindre än den maximala ordningen för en bramble.

Exempel

Varje komplett graf K _n har trebredd n - 1. Detta syns lättast med hjälp av definitionen av trädbredd när det gäller ackordgrafer: den kompletta grafen är redan ackordal, och att lägga till fler kanter kan inte minska storleken på dess största klick.

En ansluten graf med minst två hörn har trebredd 1 om och bara om det är ett träd. Ett träd har trebredd ett med samma resonemang som för kompletta grafer (det är nämligen ackord och har maximal klickstorlek två). Omvänt, om en graf har en cykel, innehåller varje ackordal komplettering av grafen minst en triangel som består av tre på varandra följande hörn av cykeln, varifrån det följer att dess trädbredd är minst två.

Gränsad trädbredd

Graffamiljer med begränsad trädbredd

För varje fast konstant k kallas trebreddens grafer högst k för partiella k -träd . Andra familjer av grafer med avgränsad trädbredd inkluderar kaktusgrafer , pseudoforest , serie -parallella grafer , yttre plana grafer , Halin -grafer och apollonska nätverk . De kontrollflödesdiagram som uppstår vid sammanställningen av strukturerade program har även begränsad treewidth, vilket gör vissa uppgifter såsom tilldelning register som ska utföras effektivt på dem.

De plana graferna har inte begränsad trädbredd, eftersom n × n -rutdiagrammet är ett plant diagram med trädbredd exakt n . Därför, om F är en mindre stängd graffamilj med begränsad trädbredd, kan den inte inkludera alla plana grafer. Omvänt, om någon plan graf inte kan förekomma som en minor för grafer i familj F , så finns det en konstant k så att alla grafer i F har högst k bred . Det vill säga att följande tre villkor motsvarar varandra:

F är en mindre sluten familj av grafer med begränsad trädbredd;
En av de oändligt många förbjudna minderåriga som kännetecknar F är plan;
F är en mindre stängd graffamilj som inte inkluderar alla plana grafer.

Förbjudna minderåriga

De fyra förbjudna minderåriga för trebredd 3: K ₅ (uppe till vänster), grafen för oktahedronen (nedre vänster), Wagner-grafen (uppe till höger) och grafen för det femkantiga prisma (nedre till höger)

För varje begränsat värde av k , kan grafen över trädbredd högst k kännetecknas av en begränsad uppsättning förbjudna minderåriga . (Det vill säga att varje graf med trebredd> k innehåller en av graferna i uppsättningen som en minor.) Var och en av dessa uppsättningar av förbjudna minderåriga innehåller minst ett plant diagram.

För k = 1 är den unika förbjudna minor en graf med tre vertexcykler .
För k = 2 är den unika förbjudna minor 4-toppunkten komplett graf K ₄ .
För k = 3 finns det fyra förbjudna minderåriga: K ₅ , grafen för oktahedronen , den femkantiga prisma -grafen och Wagner -grafen . Av dessa är de två polyhedrala graferna plana.

För större värden på k växer antalet förbjudna minderåriga minst lika snabbt som exponentiell kvadratrot av k . Kända övre gränser för storlek och antal förbjudna minderåriga är dock mycket högre än denna nedre gräns.

Algoritmer

Beräknar trädbredden

Det är NP-komplett för att avgöra om en given graf G har högst en vidbredd en given variabel k . Men när k är en fast konstant kan graferna med trädbredd k kännas igen och en bredd k trädnedbrytning konstrueras för dem i linjär tid. Tidsberoendet för denna algoritm på k är exponentiellt.

På grund av de roller som trebredden spelar på ett enormt antal fält, utvecklades olika praktiska och teoretiska algoritmer som beräknar trädets bredd på en graf. Beroende på vilken applikation som finns kan man föredra ett bättre approximationsförhållande eller bättre beroende i drifttiden från storleken på ingången eller trädbredden. Tabellen nedan ger en översikt över några av trebreddsalgoritmerna. Här är trädbredden och är antalet hörn för ett inmatningsdiagram . Var och en av algoritmerna matar ut i tid en nedbrytning av bredd som anges i kolumnen Approximation. Till exempel konstruerar algoritmen för Bodlaender (1996) i tid antingen en trädnedbrytning av inmatningsgrafen för högst bredd eller rapporterar att trädbredden är mer än . På samma sätt är algoritmen för Bodlaender et al. (2016) konstruerar antingen i tid antingen ett trädets sönderdelning av inmatningsgrafen för högst bredd eller rapporterar att trädbredden är mer än . Korhonen (2021) förbättrade detta till under samma körtid. ${\ displaystyle k}$ ${\ displaystyle n}$ ${\ displaystyle G}$ ${\ displaystyle f (k) \ cdot g (n)}$ ${\ displaystyle O (k^{O (k^{3})}) \ cdot n}$ ${\ displaystyle G}$ ${\ displaystyle k}$ ${\ displaystyle G}$ ${\ displaystyle k}$ ${\ displaystyle 2^{O (k)} \ cdot n}$ ${\ displaystyle G}$ ${\ displaystyle 5k+4}$ ${\ displaystyle G}$ ${\ displaystyle k}$ ${\ displaystyle 2k+1}$

Approximation	f (k)	g (n)	referens
exakt	${\ displaystyle O (1)}$	${\ displaystyle O (n^{k+2})}$	Arnborg, Corneil & Proskurowski (1987)
${\ displaystyle 4k+3}$	${\ displaystyle O (3^{3k})}$	${\ displaystyle O (n^{2})}$	Robertson & Seymour (1995)
${\ displaystyle 8k+7}$	${\ displaystyle 2^{O (k \ log k)}}$	${\ displaystyle n \ log ^{2} n}$	Lagergren (1996)
${\ displaystyle 5k+4}$	${\ displaystyle 2^{O (k \ log k)}}$	${\ displaystyle n \ log n}$	Reed (1992)
exakt	${\ displaystyle k^{O (k^{3})}}$	${\ displaystyle O (n)}$	Bodlaender (1996)
${\ displaystyle O (k \ cdot {\ sqrt {\ log k}})}$	${\ displaystyle O (1)}$	${\ displaystyle n^{O (1)}}$	Feige, Hajiaghayi & Lee (2008)
${\ displaystyle 4.5k+4}$	${\ displaystyle 2^{3k}}$	${\ displaystyle n^{2}}$	Amir (2010)
${\ displaystyle {\ frac {11} {3}} k+4}$	${\ displaystyle 2^{3.6982k}}$	${\ displaystyle n^{2}}$	Amir (2010)
exakt	${\ displaystyle O (1)}$	${\ displaystyle O (1.7347^{n})}$	Fomin, Todinca & Villanger (2015)
${\ displaystyle 3k+2}$	${\ displaystyle 2^{O (k)}}$	${\ displaystyle O (n \ log n)}$	Bodlaender et al. (2016)
${\ displaystyle 5k+4}$	${\ displaystyle 2^{O (k)}}$	${\ displaystyle O (n)}$	Bodlaender et al. (2016)
${\ displaystyle k^{2}}$	${\ displaystyle O (k^{7})}$	${\ displaystyle O (n \ log n)}$	Fomin et al. (2018)
${\ displaystyle 5k+4}$	${\ displaystyle 2^{8.765k}}$	${\ displaystyle O (n \ log n)}$	Belbasi & Fürer (2020)
${\ displaystyle 2k+1}$	${\ displaystyle 2^{O (k)}}$	${\ displaystyle O (n)}$	Korhonen (2021)

Olöst problem i matematik :

Kan trebredden för plana grafer beräknas på polynomtid?

(fler olösta problem i matematik)

Det är inte känt om bestämningen av planbreddens trebredd är NP-komplett, eller om deras trädbredd kan beräknas under polynomtid.

I praktiken kan en algoritm från Shoikhet & Geiger (1997) bestämma grafbredden med upp till 100 hörn och trebredden upp till 11, och hitta en ackordal komplettering av dessa grafer med den optimala trädbredden.

Lösa andra problem på grafer med liten trädbredd

I början av 1970 -talet observerades att en stor klass av kombinatoriska optimeringsproblem definierade på grafer effektivt skulle kunna lösas genom icke -seriell dynamisk programmering så länge diagrammet hade en begränsad dimension , en parameter som visade sig motsvara trädbredd av Bodlaender (1998) . Senare observerade flera författare oberoende i slutet av 1980-talet att många algoritmiska problem som är NP-kompletta för godtyckliga grafer kan lösas effektivt genom dynamisk programmering för grafer med begränsad trädbredd, med hjälp av trädets sönderdelningar av dessa grafer.

Som ett exempel kan problemet med att måla en graf med trädbredd k lösas genom att använda en dynamisk programmeringsalgoritm på en trädets sönderdelning av grafen. För varje uppsättning X _i av trädets sönderdelning och varje uppdelning av hörnen för X _i i färgklasser avgör algoritmen om den färgningen är giltig och kan utökas till alla efterkommande noder i trädets sönderdelning, genom att kombinera information från en liknande typ beräknas och lagras vid dessa noder. Den resulterande algoritmen hittar en optimal färgning av en n -vertexgraf i tiden O ( k ^{k + O (1)}n ), en tidsbunden tid som gör detta problem fixat med parametrar som kan behandlas .

Courcelles sats

För en stor klass av problem finns det en linjär tidsalgoritm för att lösa ett problem från klassen om en träd-sönderdelning med konstant begränsad trädbredd tillhandahålls. Specifikt säger Courcelles sats att om ett grafproblem kan uttryckas i logiken för grafer med hjälp av monadisk andra ordningslogik , kan det lösas i linjär tid på grafer med begränsad trädbredd. Monadic andra ordningens logik är ett språk för att beskriva graf egenskaper som använder följande konstruktioner: logiska operationer ( ), tester medlemskap (t.ex. ), kvantifieringar över hörn, kanter, uppsättningar av vertex, uppsättningar av kanter (t.ex. , , , ), adjacency test ( u är en slutpunkt för e ) och några tillägg som möjliggör saker som optimering. ${\ displaystyle \ wedge, \ vee, \ neg, \ Rightarrow}$ ${\ displaystyle e \ i E, v \ i V}$ ${\ displaystyle \ forall}$ ${\ displaystyle v \ i V}$ ${\ displaystyle \ exist}$ ${\ displaystyle e \ i E}$ ${\ displaystyle \ exist}$ ${\ displaystyle I \ subseteq V}$ ${\ displaystyle \ forall}$ ${\ displaystyle F \ subseteq E}$

Tänk till exempel på 3-färgsproblemet för grafer. För en graf frågar detta problem om det är möjligt att tilldela varje hörn en av de tre färgerna så att inte två intilliggande hörn tilldelas samma färg. Detta problem kan uttryckas i monadisk andra ordnings logik enligt följande: ${\ displaystyle G = (V, E)}$ ${\ displaystyle v \ i V}$

{\ displaystyle \ exist W_ {1} \ subseteq V: \ exist W_ {2} \ subseteq V: \ exist W_ {3} \ subseteq V: \ forall v \ in V: (v \ in W_ {1} \ vee v \ i W_ {2} \ vee v \ i W_ {3}) \ wedge}

{\ displaystyle \ forall v \ in V: \ forall w \ in V: (v, w) \ in E \ Rightarrow (\ neg (v \ in W_ {1} \ wedge w \ in W_ {1}) \ wedge \ neg (v \ i W_ {2} \ wedge w \ i W_ {2}) \ wedge \ neg (v \ i W_ {3} \ kil w \ i W_ {3}))}

,

där representerar delmängderna av hörn med var och en av de tre färgerna. Därför, genom Courcelles resultat, kan 3-färgningsproblemet lösas i linjär tid för en graf som ges en trädnedbrytning av begränsad konstant trädbredd. ${\ displaystyle W_ {1}, W_ {2}, W_ {3}}$

Relaterade parametrar

Banbredd

Den pathwidth av en graf har en mycket liknande definition för att treewidth via trädsönderdelningar, men är begränsad till trädsönderdelningar, i vilka den underliggande träd av sönderdelningen är en bana graf . Alternativt kan banbredden definieras från intervallgrafer analogt till definitionen av trädbredd från ackordgrafer. Som en konsekvens är banans bredd på en graf alltid minst lika stor som dess trädbredd, men den kan bara vara större med en logaritmisk faktor. En annan parameter, grafbandbredden , har en analog definition från korrekta intervalldiagram och är minst lika stor som banbredden. Andra relaterade parametrar inkluderar trädjupet , ett tal som är begränsat till en mindre stängd graffamilj om och bara om familjen utesluter en väg och degenerationen , ett mått på sparsiteten i en graf som högst är lika med dess trädbredd.

Rutnät mindre storlek

Eftersom treewidth av en n × n galler grafen är n , den treewidth av en graf G alltid är större än eller lika med storleken på den största kvadratgaller moll av G . I den andra riktningen visar grid -satsen av Robertson och Seymour att det finns en funktion f så att trädbredden är högst f ( r ) där r är storleken på den största fyrkantiga rutnätet. De bästa gränserna som är kända på f är att f måste vara minst Ω ( r ^d ) för någon fast konstant d > 0 och högst O ( √ r /log r ). Stramare gränser är kända för begränsade graffamiljer, vilket leder till effektiva algoritmer för många grafoptimeringsproblem på dessa familjer genom teorin om bidimensionalitet . Halins rutnätssats ger en analog av förhållandet mellan trädbredd och mindre storlek för oändliga grafer.

Diameter och lokal trädbredd

En familj F av grafer som stängs genom att ta subgrafer sägs ha begränsat den lokala trädbredden , eller diameterträbredden , om trebredden för graferna i familjen är övre begränsad av en funktion av deras diameter . Om klassen också antas vara stängd under att ta minderåriga , har F begränsat lokal trädbredd om och bara om en av de förbjudna minderåriga för F är ett toppdiagram . De ursprungliga bevisen för detta resultat visade att trebredden i en apex-minor-fri graffamilj växer högst dubbelt exponentiellt som en funktion av diametern; senare reducerades detta till enstaka exponentiell och slutligen till en linjär gräns. Avgränsad lokal trädbredd är nära besläktad med den algoritmiska teorin om tvådimensionalitet , och varje grafegenskap som kan definieras i första ordningens logik kan bestämmas för en apex-minor-fri graffamilj på en tid som bara är lite överlinjär.

Det är också möjligt att en klass av grafer som inte är stängda under minderåriga har begränsat den lokala trädbredden. I synnerhet gäller detta trivialt för en klass med grafer med begränsade grader, eftersom subgrafer med begränsad diameter har begränsad storlek. Ett annat exempel ges av 1-plana grafer , grafer som kan ritas i planet med en korsning per kant, och mer allmänt för de grafer som kan ritas på en yta av begränsat släkte med ett begränsat antal korsningar per kant. Som med mindre stängda graffamiljer med begränsad lokal trädbredd har den här egenskapen pekat vägen till effektiva approximationsalgoritmer för dessa grafer.

Hadwiger -nummer och S -funktioner

Halin (1976) definierar en klass med grafparametrar som han kallar S -funktioner, som inkluderar trädbredden. Dessa funktioner från grafer till heltal måste vara noll på grafer utan kanter , vara minor-monoton (en funktion f kallas "minor-monoton" om, när H är en minor av G , en har f (H ) ≤ f (G)), för att öka med en när en ny toppunkt tillsättes som ligger i anslutning till alla tidigare vertex, och att vidta det större värdet av de två subgrafer på vardera sidan av en klick separator . Uppsättningen av alla sådana funktioner bildar ett komplett gitter under operationerna av elementvis minimering och maximering. Det övre elementet i detta gitter är trädbredden och det nedre elementet är Hadwiger -talet , storleken på den största kompletta minor i den angivna grafen.

Anteckningar

Referenser

.

Arnborg, S .; Corneil, D .; Proskurowski, A. (1987), "Complexity of finding embeddings in a k -tree", SIAM Journal on Matrix Analysis and Applications , 8 (2): 277–284, doi : 10.1137/0608024.
Arnborg, Stefan; Proskurowski, Andrzej; Corneil, Derek G. (1990), "Forbidden minorors characterization of partial 3-trees", Diskret matematik , 80 (1): 1–19, doi : 10.1016/0012-365X (90) 90292-P , MR 1045920.
Arnborg, S .; Proskurowski, A. (1989), "Linjära tidsalgoritmer för NP-hårda problem begränsade till partiella k- träd", Diskret tillämpad matematik , 23 (1): 11–24, doi : 10.1016/0166-218X (89) 90031- 0.
Bern, MW; Lawler, EL ; Wong, AL (1987), "Linear-tid beräkning av optimala subgrafer av sönderdelbara grafer", Journal of Algorithms , 8 (2): 216-235, doi : 10,1016 / 0196-6774 (87) 90039-3.
Bertelè, Umberto; Brioschi, Francesco (1972), Nonserial Dynamic Programming , Academic Press, s. 37–38, ISBN 978-0-12-093450-8.
Bodlaender, Hans L. (1988), "Dynamisk programmering på grafer med begränsad trädbredd", Proc. 15th International Colloquium on Automata, Languages and Programming , Lecture Notes in Computer Science, 317 , Springer-Verlag, s. 105–118, CiteSeerX 10.1.1.18.8503 , doi : 10.1007/3-540-19488-6_110 , ISBN 978-3-540-19488-0.
Bodlaender, Hans L. (1996), "En linjär tidsalgoritm för att hitta trädnedbrytningar av liten trädbredd", SIAM Journal on Computing , 25 (6): 1305–1317, CiteSeerX 10.1.1.19.7484 , doi : 10.1137/S0097539793251219.
Bodlaender, Hans L. (1998), "A partial k -arboretum of graphs with bounded treeewidth", Theoretical Computer Science , 209 (1–2): 1–45, doi : 10.1016/S0304-3975 (97) 00228-4.
Bodlaender, Hans L .; Drange, Pal G .; Dregi, Markus S .; Fomin, Fedor V .; Lokshtanov, Daniel; Pilipczuk, Michal (2016), "A c^kn 5-Approximation Algorithm for Treewidth", SIAM Journal on Computing , 45 (2): 317–378, arXiv : 1304.6321 , doi : 10.1137/130947374.
Chekuri, Chandra; Chuzhoy, Julia (2016), "Polynomial bounds for the grid-minor theorem", Journal of the ACM , 63 (5): A40: 1–65, arXiv : 1305.6577 , doi : 10.1145/2820609 , MR 3593966 , S2CID 209860422.
Demaine, Erik D .; Fomin, Fedor V .; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2004), "Bidimensionella parametrar och lokal trädbredd", SIAM Journal on Discrete Mathematics , 18 (3): 501–511, CiteSeerX 10.1.1.107.6195 , doi : 10.1137/S0895480103433410 , MR 2134412.
Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2004a), "Diameter och trädbredd i mindre stängda graffamiljer, återbesökt", Algorithmica , 40 (3): 211–215, doi : 10.1007/s00453-004-1106-1 , MR 2080518 , S2CID 390856.
Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2004b), "Ekvivalens för lokal trädbredd och linjär lokal trädbredd och dess algoritmiska tillämpningar", Proceedings of the Fementhenth Annual ACM-SIAM Symposium on Discrete Algorithms , New York: ACM, s. 840–849, MR 2290974.
Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2008), "Linjäritet hos mindreåriga i trädbredd med applikationer genom bidimensionalitet" (PDF) , Combinatorica , 28 (1): 19–36, doi : 10.1007/s00493-008-2140-4 , S2CID 16520181.
Diestel, Reinhard (2004), "A short proof of Halins grid theorem", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 74 : 237–242, doi : 10.1007/BF02941538 , MR 2112834 , S2CID 124603912.
Diestel, Reinhard (2005), Graph Theory (3: e upplagan), Springer , ISBN 978-3-540-26182-7.
Reed, Bruce (1996), Effektiva parallella algoritmer för grafer över begränsad trädbredd.
Amir, Eyal (2010), Approximation Algorithms for Treewidth.
Lagergren, Jens (1992), Hitta ungefärliga separatorer och beräkna trädbredd snabbt , Association for Computing Machinery , ISBN 0897915119.

Eppstein, D. (2000), "Diameter och treewidth i mindre-sluten graffamiljer", Algorithmica , 27 (3-4): 275-291, arXiv : math / 9.907.126 , doi : 10,1007 / s004530010020 , MR 1.759.751 , S2CID 3.172.160.
Feige, Uriel; Hajiaghayi, MohammadTaghi; Lee, James R. (2008), "Improved Approximation Algorithms for Minimum Weight Vertex Separators", SIAM Journal on Computing , 38 (2): 629–657, CiteSeerX 10.1.1.597.5634 , doi : 10.1137/05064299X.
Frick, Markus; Grohe, Martin (2001), "Bestämning av första ordningens egenskaper hos lokalt trädnedbrytbara strukturer", Journal of the ACM , 48 (6): 1184–1206, arXiv : cs/0004007 , doi : 10.1145/504794.504798 , MR 2143836 , S2CID 999472.
Fomin, Fedor V .; Lokshtanov, Daniel; Saurabh, Saket; Pilipczuk, Michal; Wrochna, Marcin (2018), "Fully Polynomial Time Parameterized Computations for Graphs and Matrices of Low Treewidth", ACM Trans. Algoritmer , 14 (3): 34: 1–34: 45, arXiv : 1511.01379 , doi : 10.1145/3186898 , S2CID 2144798.
Grigoriev, Alexander; Bodlaender, Hans L. (2007), "Algoritmer för grafer Inbäddningsbar med få korsningar per kant", Algorithmica , 49 (1): 1-11, CiteSeerX 10.1.1.65.5071 , doi : 10,1007 / s00453-007-0010-x , MR 2344391 , S2CID 8174422.
Halin, Rudolf (1976), " S -funktioner för grafer", Journal of Geometry , 8 (1–2): 171–186, doi : 10.1007/BF01917434 , S2CID 120256194.
Kao, Ming-Yang, red. (2008), "Treewidth of graphs", Encyclopedia of Algorithms , Springer, sid. 969, ISBN 9780387307701, Ett annat mångårigt öppet problem är om det finns en polynom-tidsalgoritm för att beräkna trädbredden för plana grafer.
Korhonen, Tuukka (2021), Single-Exponential Time 2-Approximation Algorithm for Treewidth , arXiv : 2104.07463
Belbasi, Mahdi; Fürer, Martin (2020), En förbättring av Reed's Treewidth Approximation , arXiv : 2010.03105
Lagergren, Jens (1993), "En övre gräns för storleken på ett hinder", Graph structure theory (Seattle, WA, 1991) , Contemporary Mathematics, 147 , Providence, RI: American Mathematical Society, s. 601–621, doi : 10.1090/conm/147/01202 , ISBN 9780821851609, MR 1224734.
Ramachandramurthi, Siddharthan (1997), "Strukturen och antalet hinder för trädbredd", SIAM Journal on Discrete Mathematics , 10 (1): 146–157, doi : 10.1137/S0895480195280010 , MR 1430552.
Robertson, Neil ; Seymour, Paul D. (1984), "Graph minors III: Planar tree-width", Journal of Combinatorial Theory, Series B , 36 (1): 49–64, doi : 10.1016/0095-8956 (84) 90013-3.
Robertson, Neil ; Seymour, Paul D. (1986), "Graph minderåriga V: Exklusive en plan graf", Journal of Combinatorial Theory, Series B , 41 (1): 92–114, doi : 10.1016/0095-8956 (86) 90030-4.
Robertson, Neil ; Seymour, Paul D. (1995), "Graph Minors XIII: The Disjoint Paths Problem", Journal of Combinatorial Theory, Series B , 63 (1): 65–110, doi : 10.1006/jctb.1995.1006.
Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1994), "Snabbt exklusive en plan graf", Journal of Combinatorial Theory , Series B, 62 (2): 323–348, doi : 10.1006/jctb.1994.1073 , MR 1305057.
Satyanarayana, A .; Tung, L. (1990), "A characterization of partial 3-trees", Networks , 20 (3): 299–322, doi : 10.1002/net.3230200304 , MR 1050503.
Seymour, Paul D .; Thomas, Robin (1993), "Graph Searching and a Min-Max Theorem for Tree-Width.", Journal of Combinatorial Theory, Series B , 58 (1): 22–33, doi : 10.1006/jctb.1993.1027.
Shoikhet, Kirill; Geiger, Dan (1997), "En praktisk algoritm för att hitta optimala trianguleringar", Proc. AAAI '97 (PDF) , s. 185–190.
Thorup, Mikkel (1998), "Alla strukturerade program har liten trädbredd och bra registerallokering", Information och beräkning , 142 (2): 159–181, doi : 10.1006/inco.1997.2697.
Fomin, Fedor V .; Todinca, Ioan; Villanger, Yngve (2015), "Large Induced Subgraphs via Triangulations and CMSO", SIAM Journal on Computing , 44 (1): 54–87, arXiv : 1309.1559 , doi : 10.1137/140964801 , S2CID 15880453.

Languages

In other projects