Faszélesség
A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf faszélessége vagy favastagsága (treewidth) egy a gráf szerkezetétől függő, a gráfhoz rendelt szám, azaz gráftulajdonság. A faszélesség több, egymással egyenértékű módon definiálható: a gráf fafelbontása legnagyobb csúcshalmazával, a gráf merev körű kiegészítésében található legnagyobb klikkel, a gráfon játszott üldözős-menekülős játék elkerülési stratégiáját leíró menedékkel vagy az egymást kölcsönösen érintő összefüggő részgráfok, azaz bramble-ök maximális rendjével.
A faszélesség gyakran előkerül gráfalgoritmusok parametrikus bonyolultságának vizsgálatakor. A legfeljebb k faszélességű gráfokat részleges k-fáknak is nevezik; számos, részletekbe menően tanulmányozott gráfcsalád rendelkezik korlátozott faszélességgel.
A faszélesség koncepciója először Umberto Bertelé and Francesco Brioschi (1972)-nél jelent meg „dimenzió” név alatt. Később Rudolf Halin (1976) fedezte fel újra, a Hadwiger-számmal közös tulajdonságai alapján. Majd Neil Robertson and Paul Seymour (1984) ismét felfedezték, és azóta számos más szerző is tanulmányozta.[1]
Definíció
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Tree_decomposition.svg/240px-Tree_decomposition.svg.png)
Egy G = (V, E) gráf fafelbontása alatt olyan T fát értünk, az X1, ..., Xn csomópontokkal, ahol mindegyik Xi a V részhalmaza, mely a következő tulajdonságoknak megfelel[2] (a csomópont alatt T egy-egy csúcsát értjük, hogy elkerüljük a G csúcsaival való összekeverésüket):
- Az Xi halmazok uniója megegyezik V-vel. Tehát a gráf minden csúcsát tartalmazza legalább egy facsomópont.
- Ha Xi és Xj is tartalmaz egy v csúcsot, akkor az Xi és Xj közötti (egyedi) úton lévő minden T-beli Xk csomópontnak is tartalmaznia kell v-t. Ezzel ekvivalens megfogalmazás szerint, a v-t tartalmazó facsomópontok a T összefüggő részfáját alkotják.
- A gráf minden (v, w) éléhez tartozik egy Xi részhalmaz, ami v-t és w-t is tartalmazza. Tehát a gráf csúcsai akkor lehetnek szomszédosak, ha a nekik megfelelő részfáknak van egy közös csomópontja.
A fafelbontás szélessége a legnagyobb Xi halmaz mérete mínusz egy. A G gráf tw(G) faszélessége a G összes lehetséges fafelbontásai közül a minimális szélesség. Ebben a definícióban azért csökkentjük eggyel a legnagyobb halmaz méretét, hogy egy fa szélessége éppen eggyel legyen egyenlő.
Ezzel ekvivalens definíció szerint a G faszélessége eggyel kisebb, mint a legkisebb klikkszámú, G-t tartalmazó merev körű gráf legnagyobb klikkje. Ilyen klikkméretű merev körű gráfot elő lehet állítani úgy, hogy G-nek minden olyan két csúcsa közé behúzunk egy élt, melyek közül mindkettő legalább egy halmazba beletartozik az Xi-t közül.
A faszélesség jellemezhető az üldözős-menekülős játék elkerülési stratégiáját leíró menedékek segítségével is. Egy G gráf faszélessége pontosan akkor k, ha létezik benne k + 1 rendű menedék, de magasabb rendű már nem. Egy k + 1 rendű menedék olyan β függvény, ami G minden, legfeljebb k csúcsot tartalmazó X csúcshalmazához hozzárendeli G \ X valamely összefüggő komponensét, és amire igaz az a monotonitási feltétel, miszerint ha X ⊆ Y, akkor β(Y) ⊆ β(X).
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5a/3x3_grid_graph_haven.svg/220px-3x3_grid_graph_haven.svg.png)
Hasonló jellemzés adható az egymást kölcsönösen érintő (vagy közös csúccsal rendelkező, vagy éllel összekötött) összefüggő részgráfok, a bramble-ök segítségével.[3] A bramble rendje a részgráfok családjának legkisebb „hitting set”-je (olyan halmaz, ami minden halmaz elemei közül legalább egyet tartalmaz), a gráf faszélessége pedig eggyel kisebb a bramble maximális rendjénél.
Példák
Minden Kn teljes gráf faszélessége n − 1. Ez a legkönnyebben a merev körű gráfos definícióból látható be: a teljes gráf eleve merev körű, és újabb él hozzáadásával nem lehet csökkenteni a legnagyobb klikkjének a méretét.
Egy összefüggő, legalább két csúcsból álló gráf faszélessége pontosan akkor 1, ha a gráf fa. A fa szélessége a teljes gráfokhoz hasonlóan látható be (merev körű, és maximális elemszámú klikkje 2). Megfordítva, ha egy gráfnak van köre, akkor a gráf minden merev körű kiegészítésében legalább egy háromszög egymást követő csúcsa szerepel, amiből következik, hogy a faszélesség legalább kettő.
Korlátos faszélesség
Korlátos faszélességű gráfcsaládok
Rögzített k értékekre, a legfeljebb k faszélességű gráfokat részleges k-fáknak nevezik. A korlátos faszélességű gráfcsaládok közé tartoznak a kaktuszgráfok, pszeudoerdők, soros-párhuzamos gráfok, külsíkgráfok, Halin-gráfok és Apollóniusz-hálózatok.[4] A strukturált programok lefordításakor létrejövő vezérlésfolyam-gráf faszélessége szintén korlátos, ami lehetővé teszi bizonyos feladatok, például a regiszterallokáció hatékony végrehajtását.[5]
A síkbarajzolható gráfok faszélessége nem korlátos, hiszen az n × n-es rácsgráf olyan síkbarajzolható gráf, melynek faszélessége pontosan n. Ezért ha F egy korlátos faszélességű, minorzárt gráfcsalád, akkor nem tartalmazhatja az összes síkbarajzolható gráfot. Megfordítva, ha valamely síkbarajzolható gráf nem jelenik meg egy F gráfcsalád minoraként, akkor létezik olyan k konstans, melyre az összes F-beli gráf faszélessége legfeljebb k. Más szavakkal, a következő három feltétel egymással egyenértékű:[6]
- F korlátozott faszélességű gráfok minorzárt családja;
- Az F-et jellemző véges sor tiltott minor közül valamelyik síkba rajzolható;
- F minorzárt gráfcsalád, ami nem tartalmazza az összes síkbarajzolható gráfot.
Tiltott minorok
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Partial_3-tree_forbidden_minors.svg/300px-Partial_3-tree_forbidden_minors.svg.png)
Minden véges k értékre a legfeljebb k faszélességű gráfok jellemezhetők tiltott minorok egy véges halmazával. (Tehát bármely k-nál nagyobb faszélességű gráf tartalmazza ezen obstrukciós halmaz tiltott gráfjainak valamelyikét minorként.) Minden ilyen véges obstrukciós halmaz tartalmaz legalább egy síkbarajzolható gráfot.
- A k = 1 esetben az egyedüli tiltott minor a 3 csúcsú körgráf, K3.[7]
- A k = 2 esetben az egyedüli tiltott minor a 4 csúcsú teljes gráf, K4.[7]
- A k = 3 esetben már négy tiltott minor van: a K5 teljes gráf, az oktaéder gráfja, a GP(5,1) ötszög alapú hasábgráf és a Wagner-gráf. Ezek közül a két poliédergráf síkba rajzolható.[8]
A k = 4 esetben már legalább 75 tiltott minort találtak, és a k növekedésével a tiltott minorok száma legalább a k négyzetgyöke szerint exponenciálisan nő.[9] Az ismert felső korlátok a tiltott minorok méretére és számára azonban sokkal nagyobbak ennél az alsó korlátnál.[10]
Algoritmusok
A faszélesség meghatározása
Annak meghatározása, hogy adott G gráf faszélessége adott k értékét meghaladja-e, NP-teljes probléma.[11] Ennek ellenére k rögzített értékére a pontosan k faszélességű gráfok felismerhetők, és k szélességű fafelbontásuk is előállítható lineáris időben.[12] Ezen algoritmus időfüggése k szerint exponenciális.
![]() | A matematika megoldatlan problémája: Meghatározható-e a síkbarajzolható gráfok faszélessége polinom időben? (A matematika további megoldatlan problémái) |
Nem ismert, hogy a síkbarajzolható gráfok faszélességének meghatározása NP-teljes, vagy polinom időben meghatározható-e.[13]
A gyakorlatban (Shoikhet & Geiger 1997) algoritmusa képes a legfeljebb 100 csúcsból álló gráfok faszélességének meghatározására legfeljebb 11 értékig, optimális faszélességű merev körű kiegészítés keresésével.
Egyéb problémák megoldása alacsony faszélességű gráfokon
Az 1970-es évek elején megfigyelték, hogy a gráfokon definiált kombinatorikai optimalizációs problémák nagy osztálya hatékonyan megoldható nem soros, dinamikus programozási módszerekkel, amennyiben a gráf korlátos „dimenzióval” rendelkezik,[14] mely paraméterről (Bodlaender 1998) megmutatta, hogy a faszélességgel ekvivalens. Később egymástól függetlenül több szerző is megfigyelte az 1980-as évek végén,[15] hogy számos, tetszőleges gráfokon NP-teljes probléma a korlátos faszélességű gráfokon dinamikus programozással hatékonyan megoldható, a gráfok fafelbontásának felhasználásával.
Példa erre a k faszélességű gráf színezése. A fafelbontás minden Xi halmazára, és az Xi csúcsainak minden színosztályba sorolására az algoritmus meghatározza, hogy a színezés érvényes-e, illetve kiterjeszthető-e a a fefelbontás leszármazó csomópontjaira, a csomópontokon tárolt hasonló információk felhasználásával. A végső algoritmus egy n csúcsú gráf optimális színezését O(kk + O(1)n) időben oldja meg, ami ezt a problémát rögzített paraméter mellett kezelhetővé teszi.
Courcelle-tétel
![]() | Bővebben: Courcelle-tétel |
Egy nagy problémaosztályra létezik lineáris idejű megoldó algoritmus, ha bemenetként egy konstans, korlátos faszélességű fafelbontást adunk meg. A Courcelle-tétel[16][17] állítása szerint ha egy gráfprobléma kifejezhető monadikus másodrendű logika szerinti gráflogika segítségével, akkor korlátos faszélességű gráfokon lineáris időben megoldható. A monadikus másodrendű logika a gráftulajdonságokat a következő konstrukciók segítségével írja le: logikai műveletek (), tartalmazás ellenőrzése (pl. ), kvantorok csúcsokra és élekre, illetve csúcsok és élek halmazára (pl. , , , ), illeszkedés ellenőrzése (u az e végpontja), valamint egy optimalizáló kiterjesztés.
Tekintsük például a gráfok 3-színezési problémáját. Egy gráf esetén azt kérdezzük, lehetséges-e minden csúcshoz a 3 szín egyikét hozzárendelni úgy, hogy semelyik két szomszédos csúcs ne legyen egymással megegyező színű. A probléma így fejezhető ki monadikus másodrendű logikával:
- ,
ahol az egyes színosztályba tartozó csúcs-részhalmazoknak felelnek meg. Tehát Courcelle tétele szerint a 3-színezési probléma lineáris időben megoldható egy konstans faszélességű gráfon, ha annak fafelbontása adott.
Kapcsolódó paraméterek
Útszélesség
Egy gráf útszélessége a faszélességhez nagyon hasonlóan definiálható, de olyan fafelbontásokra korlátozódik, melyben kizárólag útgráfok szerepelnek. Alternatív megoldásként az útszélesség definiálható intervallumgráfok segítségével, hasonlóan a faszélesség merev körű gráfokkal való definiálásához. A gráfok útszélessége az eddigiekből következően legalább akkora, mint a faszélességük, de legfeljebb logaritmikus faktorral lehet nagyobb.[4] Egy másik paramétert, a sávszélességet egység-intervallumgráffal definiálják, és legalább akkora, mint az útszélesség. További kapcsolódó paraméter a famélység, ami egy minorzárt gráfcsaládnál akkor korlátos, ha a család tiltott gráfja egy út, valamint a degeneráltság, a gráfok ritkaságának egy mértéke, ami legfeljebb a faszélességgel egyezik meg.
Rácsminor-méret
Mivel egy n × n méretű négyzetes rácsgráf faszélessége n, egy G gráf faszélessége mindig nagyobb vagy egyenlő, mint G legnagyobb rácsgráf-minorának mérete. Megfordítva, a Robertson és Seymour által kimondott rácsminor-tétel (grid minor theorem) szerint létezik olyan f függvény, melyre a faszélesség legfeljebb f(r), ahol r a legnagyobb négyzetrács-minor mérete.[18] Az f-re vonatkozó legjobb korlátok szerint f legalább Ω(rd) valamely rögzített d>0 konstansra, de legfeljebb O(√r/log r).[19] Egyes korlátozott gráfcsaládokra szorosabb korlátok ismertek, melyekre vonatkozó gráfoptimalizálási problémákra hatékony algoritmusokat ad a bidimenzionalitás-elmélet.[20] A Halin-rácstétel a faszélesség és rácsminor-méret között állít fel összefüggést végtelen gráfokra.[21]
Átmérő és lokális faszélesség
Egy F gráfcsaládnak akkor van korlátos helyi faszélessége (bounded local treewidth), illetve rendelkezik az átmérő-faszélesség tulajdonsággal (diameter-treewidth property), ha a család gráfjainak faszélességét felülről korlátozza átmérőjük egy függvénye. Ha F minden minora szintén F-ben található, akkor F pontosan akkor rendelkezik korlátos helyi faszélességgel, ha F valamelyik tiltott minora egy csúcsgráf.[22] Ennek az eredménynek az eredeti bizonyításában szerepelt annak bizonyítása is, hogy egy csúcsminor-mentes gráfcsalád faszélessége legfeljebb az átmérő dupla-exponenciális függvényében nő;[23] ezt később sikerült sima exponenciálisra[20], majd lineáris korlátra javítani.[24] Az átmérő-faszélesség tulajdonság közeli kapcsolatban áll a bidimenzionalitás algoritmikus elméletével,[25] és minden elsőrendű logikával definiálható gráftulajdonság létezése egy csúcsminor-mentes gráfcsalád esetében eldönthető a lineárisnál csak kissé rosszabb – O(n1+(1/k) – időben.[26]
Lehet korlátos helyi faszélessége nem minorzárt gráfosztálynak is. Ilyenek például az élenként legfeljebb egy metszéssel síkba rajzolható ún. 1-síkbarajzolható gráfok, vagy általánosabban azok a gráfok, melyek egy korlátos génuszú felületre élenként korlátozott számú metszéssel lerajzolhatók. Ahogy a minorzárt gráfcsaládoknál, a korlátos helyi faszélesség itt is hatékony approximációs algoritmusoknak enged utat.[27]
Hadwiger-szám és S-függvények
(Halin 1976) egy általa S-függvényeknek (S-functions) nevezett gráfparaméter-osztályt definiál, melybe a faszélesség is beletartozik. Ezeknek a gráfokhoz egész számokat rendelő függvényeknek a következő tulajdonságokkal kell rendelkezniük: az üres gráfon legyen nulla az értékük, legyenek minor-monotonok,[28] értékük eggyel nőjön, ha az összes korábbi csúccsal szomszédos új csúcs kerül a gráfba, végül hogy egy klikk-szeparátor két oldalán lévő részgráfok értékei közül a nagyobbikat vegye fel. Az összes ilyen függvény halmaza az elemenkénti minimalizáció és maximalizáció műveleteire nézve teljes hálót alkot. A háló legkisebb eleme a Hadwiger-szám, azaz a legnagyobb teljesgráf-minor mérete, a legnagyobb pedig a faszélesség.
Fordítás
- Ez a szócikk részben vagy egészben a Treewidth című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
- ↑ (Diestel 2005) pp.354–355
- ↑ (Diestel 2005) section 12.3
- ↑ (Seymour & Thomas 1993).
- ↑ a b (Bodlaender 1998).
- ↑ (Thorup 1998).
- ↑ (Robertson & Seymour 1986).
- ↑ a b (Bodlaender 1988).
- ↑ (Arnborg, Proskurowski & Corneil 1990); (Satyanarayana & Tung 1990).
- ↑ Ramachandramurthi (1997).
- ↑ Lagergren (1993).
- ↑ Arnborg, Corneil & Proskurowski (1987).
- ↑ (Bodlaender 1996).
- ↑ Kao (2008).
- ↑ Bertelé & Brioschi (1972).
- ↑ (Arnborg & Proskurowski 1989); (Bern, Lawler & Wong 1987); (Bodlaender 1988).
- ↑ Courcelle, B. (1990. augusztus 9.). „The monadic second-order logic of graphs I: Recognizable sets of finite graphs”. Information and Computation 85, 12–75. o. DOI:10.1016/0890-5401(90)90043-h.
- ↑ Courcelle, B. (1992. augusztus 9.). „The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues.”. Informatique Théorique (26), 257–286. o.
- ↑ Robertson, Seymour. Graph minors. V. Excluding a planar graph. [1]
- ↑ (Chekuri & Chuzhoy 2016). Az alsó korlátban látható Ω jelöléshez lásd O jelölés.
- ↑ a b Demaine & Hajiaghayi (2008).
- ↑ Diestel (2004).
- ↑ Eppstein (2000).
- ↑ (Eppstein 2000); (Demaine & Hajiaghayi 2004a).
- ↑ Demaine & Hajiaghayi (2004b).
- ↑ (Demaine et al. 2004); (Demaine & Hajiaghayi 2008).
- ↑ Frick & Grohe (2001).
- ↑ Grigoriev & Bodlaender (2007).
- ↑ Az f függvény akkor minor-monoton, ha fennáll, hogy ha H a G minora, akkor f(H) ≤ f(G).
Források
- 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 minors characterization of partial 3-trees", Discrete Mathematics 80 (1): 1–19, DOI 10.1016/0012-365X(90)90292-P
- Arnborg, S. & Proskurowski, A. (1989), "Linear time algorithms for NP-hard problems restricted to partial k-trees", Discrete Applied Mathematics 23 (1): 11–24, DOI 10.1016/0166-218X(89)90031-0
- Bern, M. W.; Lawler, E. L. & Wong, A. L. (1987), "Linear-time computation of optimal subgraphs of decomposable graphs", 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, pp. 37–38, ISBN 0-12-093450-7, <https://books.google.ca/books?id=baw3LMwm-y8C&pg=PA37>
- Bodlaender, Hans L. (1988), "Dynamic programming on graphs with bounded treewidth", Proc. 15th International Colloquium on Automata, Languages and Programming, vol. 317, Lecture Notes in Computer Science, Springer-Verlag, pp. 105–118, DOI 10.1007/3-540-19488-6_110
- 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
- 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
- Chekuri, Chandra & Chuzhoy, Julia (2016), "Polynomial bounds for the grid-minor theorem", Journal of the ACM 63 (5): A40:1–65, DOI 10.1145/2820609
- Demaine, Erik D.; Fomin, Fedor V. & Hajiaghayi, MohammadTaghi et al. (2004), "Bidimensional parameters and local treewidth", SIAM Journal on Discrete Mathematics 18 (3): 501–511, DOI 10.1137/S0895480103433410
- Demaine, Erik D. & Hajiaghayi, MohammadTaghi (2004a), "Diameter and treewidth in minor-closed graph families, revisited", Algorithmica 40 (3): 211–215, DOI 10.1007/s00453-004-1106-1
- Demaine, Erik D. & Hajiaghayi, MohammadTaghi (2004b), "Equivalence of local treewidth and linear local treewidth and its algorithmic applications", Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New York: ACM, pp. 840–849
- Demaine, Erik D. & Hajiaghayi, MohammadTaghi (2008), "Linearity of grid minors in treewidth with applications through bidimensionality", Combinatorica 28 (1): 19–36, doi:10.1007/s00493-008-2140-4, <http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf>
- Diestel, Reinhard (2004), "A short proof of Halin's grid theorem", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 74: 237–242, DOI 10.1007/BF02941538
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6, <http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/>
- Eppstein, D. (2000), "Diameter and treewidth in minor-closed graph families", Algorithmica 27 (3-4): 275–291, DOI 10.1007/s004530010020
- Frick, Markus & Grohe, Martin (2001), "Deciding first-order properties of locally tree-decomposable structures", Journal of the ACM 48 (6): 1184–1206, DOI 10.1145/504794.504798
- Grigoriev, Alexander & Bodlaender, Hans L. (2007), "Algorithms for graphs embeddable with few crossings per edge", Algorithmica 49 (1): 1–11, DOI 10.1007/s00453-007-0010-x
- Halin, Rudolf (1976), "S-functions for graphs", Journal of Geometry 8: 171–186, DOI 10.1007/BF01917434
- Kao, Ming-Yang, ed. (2008), "Treewidth of graphs", Encyclopedia of Algorithms, Springer, p. 969, ISBN 9780387307701, <https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA969>
- Lagergren, Jens (1993), "An upper bound on the size of an obstruction", Graph structure theory (Seattle, WA, 1991), vol. 147, Contemporary Mathematics, Providence, RI: American Mathematical Society, pp. 601–621, DOI 10.1090/conm/147/01202
- Ramachandramurthi, Siddharthan (1997), "The structure and number of obstructions to treewidth", SIAM Journal on Discrete Mathematics 10 (1): 146–157, DOI 10.1137/S0895480195280010
- 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 minors V: Excluding a planar graph", Journal of Combinatorial Theory, Series B 41 (1): 92–114, DOI 10.1016/0095-8956(86)90030-4
- Robertson, Neil; Seymour, Paul & Thomas, Robin (1994), "Quickly excluding a planar graph", Journal of Combinatorial Theory, Series B 62 (2): 323–348, DOI 10.1006/jctb.1994.1073
- Satyanarayana, A. & Tung, L. (1990), "A characterization of partial 3-trees", Networks 20 (3): 299–322, DOI 10.1002/net.3230200304
- 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), "A practical algorithm for finding optimal triangulations", Proc. AAAI '97, pp. 185–190, <http://www.aaai.org/Papers/AAAI/1997/AAAI97-029.pdf>
- Thorup, Mikkel (1998), "All structured programs have small tree width and good register allocation", Information and Computation 142 (2): 159–181, DOI 10.1006/inco.1997.2697