Radan leveys

Graafiteoriassa graafin G polun hajotelma on epävirallisesti graafin G  esitys "paksutettuna" poluna [1] ja graafin G polun leveys  on luku, joka mittaa kuinka paljon graafi G on ollut paksuuntunut. Muodollisemmin polkujakelu on graafin G osajoukon kärkijono siten, että kunkin reunan loppupisteet esiintyvät yhdessä osajoukosta ja jokainen kärki kuuluu (ainakin) yhteen joukoista [2] , ja polun leveys on yksi pienempi kuin suurimman joukon koko tällaisessa hajotuksessa. Radan leveys tunnetaan myös intervallipaksuutena .(yksi pienempi kuin graafin G intervallisupergraafin suurimman klikkin koko ), kärkijaon arvo tai kärkihakunumero [3] [4] .

Polun leveys ja polun hajottelu ovat läheisesti analogisia puun leveyden ja puun hajoamisen kanssa . Niillä on keskeinen rooli graafimoorillien teoriassa -  graafiperheet, jotka ovat suljettuja graafien alapuolella ja jotka eivät sisällä kaikkia metsiä , voidaan luonnehtia rajallisen polunleveyteen [2] , ja yleisessä rakenteessa syntyvät "pyörteet" alaikäisten suhteen suljettujen graafiperheiden teorialla on rajoitettu polun leveys [5] . Polunleveyden ja rajatun polunleveyden kaavioilla on sovelluksia VLSI -tekniikassa , graafien visualisoinnissa ja laskennallisessa lingvistiikassa .

Ongelma mielivaltaisten graafien polunleveyden löytämisessä on NP-kova . Lisäksi jopa polun leveyden tarkan approksimoinnin ongelma on NP-kova [6] [7] . Tämä ongelma on kuitenkin kiinteäparametrisesti ratkaistava –  testata, onko graafilla polunleveys k , voidaan ratkaista ajassa, joka on lineaarinen graafin koossa mutta supereksponentiaalinen k :ssä [8] Lisäksi joillekin erityisille graafiluokille, kuten esim. puut , polun leveys voidaan laskea polynomiajassa riippumatta k :stä [9] [10] . Monet graafiteorian ongelmat voidaan ratkaista tehokkaasti rajallisen polunleveyden kuvaajilla käyttämällä dynaamista ohjelmointia graafin polun hajottelussa [11] . Puuhajottelua voidaan käyttää myös dynaamisten ohjelmointialgoritmien kapasiteetin monimutkaisuuden arvioimiseen graafisissa puunleveyksissä [12] .

Määritelmä

Robertson ja Seymour [2] määrittelivät ensimmäisessä kuuluisassa graafin mollikirjoituksia käsittelevässä artikkelisarjassa graafin G polun hajotuksen graafin G kärkien osajoukkojen X i sekvenssiksi, jolla on kaksi ominaisuutta:

1. Jokaiselle reunalle G on i sellainen, että molemmat reunan päätepisteet kuuluvat osajoukkoon X i
2. Kaikille kolmelle indeksille i ≤ j ≤ k , X i ∩ X k ⊆ X j .

Toinen näistä kahdesta ominaisuudesta vastaa vaatimusta, että minkä tahansa kärjen sisältävät osajoukot muodostavat koko sekvenssin jatkuvan osajonon. Robertsonin ja Seymourin myöhemmissä graafisen mollisarjan kielessä polkuhajotelma on ( X , T ) puuhajotelma, jossa taustalla oleva hajotuspuu T on polku .

Polun hajotusleveys määritellään samalla tavalla kuin puuhajotelmalle, eli max i  | X i | − 1, ja graafin G polun leveys on yhtä suuri kuin graafin G kaikkien polkujaottelujen minimileveys . Yhden vähentämisellä X i : n koosta tässä määritelmässä on vain vähän vaikutusta useimpiin polunleveyden sovelluksiin, mutta se tekee polunleveydestä yhtä suuren kuin yksi.

Vaihtoehtoiset kuvaukset

Kuten Bodlaender [3] kirjoittaa , polunleveyttä voidaan kuvata monilla vastaavilla tavoilla.

Liimaussekvenssit

Puuhajotus voidaan kuvata graafien G i sekvenssinä , jotka liimataan yhteen tunnistamalla sekvenssin vierekkäisten graafien kärkipareja, ja tämän liimauksen tuloksena muodostuu graafi G . Graafeina G i voimme ottaa generoidut osagraafit joukoista X i polun hajotuksen ensimmäisessä määrittelyssä, liimaamalla pisteet vierekkäisiin generoituihin aligraafiin, jos nämä pisteet on generoitu G :n samasta kärjestä . Toisessa suunnassa voidaan ottaa X i graafien G i kärkijoukoiksi . Puun hajotuksen leveys on tällöin yksi pienempi kuin yhden graafin G i [2] pisteiden maksimimäärä .

Intervallipaksuus

Minkä tahansa graafin G polun leveys on yksi pienempi kuin G :n aligraafina sisältävän väligraafin pienin klikkiluku [14] . Toisin sanoen mille tahansa graafin G puuhajotelmalle voidaan löytää intervalli-supergraafi ja mille tahansa intervalli-supergraafille G voidaan löytää graafin G puuhajotelma, jonka hajotusleveys on yksi pienempi kuin intervallikaavion klikkiluku. .

Yhdessä suunnassa oletetaan, että graafin G puuhajotelma on annettu. Sitten voidaan esittää hajotuksen kärjet pisteinä viivalla (samassa järjestyksessä, jossa ne tulevat polulle) ja esittää jokainen kärki v suljettuna intervallina, jossa nämä pisteet ovat päätepisteitä. Olkoon esimerkiksi ( X 1 , . . . , X r ) graafin G polkujakelu , pisteet viivalla [1, . . . , r], niin kärjen v esitys on väli . Tällöin v:n sisältävien kärkien puuhajotelma vastaa välin v :n esittämistä (eli päätepisteitä) . G :n pisteistä muodostettu intervallileikkausgraafi on väligraafi , joka sisältää G :n aligraafina. Sen maksimiklikit saadaan edustavat pisteet sisältävästä intervallijoukosta, ja niiden suurin klikkin koko on yhtä suurempi kuin graafin G polun leveys .

Toisessa suunnassa, jos G on intervalligraafin aligraafi, jonka klikkiluku on p  + 1, niin G :llä on puuhajotelma, jonka leveys on p , jonka kärjet annetaan intervalligraafin maksimiklikeillä . Esimerkiksi kuviossa esitetyllä intervallikaaviolla on puuhajotelma, jossa on viisi kärkeä, jotka vastaavat viittä maksimiklikkiä ABC , ACD , CDE , CDF ja FG . Maksimiklikin koko on kolme ja tämän puun hajoamisen leveys on kaksi.

Tämä polunleveyden ja intervallipaksuuden välinen ekvivalenssi on läheinen analogia puunleveyden ja vähimmäisklikkien lukumäärän (miinus yksi) välillä sointukuvaajassa , jonka aligraafi on annettu graafi . Intervallikaaviot ovat sointukaavioiden erikoistapaus, ja sointukuvaajat voidaan esittää yleisten puiden alipuun leikkauskaavioina, mikä yleistää lähestymistavan, jossa intervallikaaviot tulkitaan polun osapolun leikkauskaavioiksi.

Vertex split summa

Oletetaan, että graafin G kärjet ovat lineaarisesti järjestetyt . Tällöin G :n kärkiosion suuruus on pienin luku s siten, että jokaisessa kärjessä v korkeintaan s kärkeä edeltää v :tä järjestyksessä, jolla on v tai jokin seuraavista pisteistä sen naapurissa. Kuvaajan G kärjen jaon arvo on minkä tahansa graafin G lineaarisen lineaarisen järjestyksen minimipisteen jakoarvo . Ellis, Sudborough ja Turner [15] ottivat käyttöön kärjen jaon arvon, ja se on yhtä suuri kuin graafin G polun leveys [16] [17] . Tämä seuraa aiemmin mainitusta intervallikaavioiden ja klikkilukujen ekvivalenssista - jos G on intervalligraafin I osagraafi, joka on esitetty (kuten kuvassa) siten, että intervallien kaikki päät ovat erilaisia, niin graafin I välien vasemmilla päillä on kärkien erotusarvo yksi pienempi kuin sarakkeen I klikkiluvut . Toisessa suunnassa G :n lineaarisesta järjestyksestä voidaan saada intervalliesitys, jossa kärjen v välin vasen päätepiste on järjestyksen paikka ja oikea päätepiste on v :n viimeisen naapurin sijainti. tilaus.

Vertex-hakunumero

Parhaiten löydetty kaavion peli on eräänlainen takaa-ajo- välttöpeli, jossa useat takaa-ajat työskentelevät yhdessä jäljittääkseen kaaviossa piileskelevän karkun. Takaajat sijoitetaan graafin kärkipisteisiin, kun taas pakolainen voi sijaita graafin missä tahansa reunassa, hänen sijaintinsa ja liikkeensä eivät ole takaa-ajoille näkyvissä. Seuraavan liikkeen aikana osa (tai kaikki) takaa-ajoista voi siirtyä (mielivaltaisesti, ei välttämättä reunoja pitkin) yhdestä kärjestä toiseen, ja sitten pakolainen liikkuu mitä tahansa graafin polkua pitkin, mutta ei voi kulkea graafin käyttämien kärkien läpi. takaa-ajoille. Karkolainen jää kiinni, kun hänen kaaren molemmissa päissä on takaa-ajia. Graafin kärkihaun numero on takaa-ajien vähimmäismäärä, joka tarvitaan takaamaan pakolaisen vangitseminen hänen käyttäytymisestään riippumatta. Kuten Kyrouzis ja Panadimitriou [18] osoittivat , graafin vertex-hakunumero on yhtä suuri kuin sen intervallipaksuus. Takaajien optimaalinen strategia on liikkeet, joissa takaa-ajat muodostavat peräkkäin erottavia lineaarisen järjestyksen sarjoja minimipisteiden erolla.

Reunat

Graafilla, jossa on n kärkeä ja polun leveys k , on enintään k ( n − k + ( k − 1)/2)) reunaa ja maksimigraafit polun leveydellä k (kuvaajat, joihin ei voida lisätä reunaa polkua suurentamatta leveys) on reunojen lukumäärä. Maksimigraafin, jonka polun leveys k on oltava joko k -polku tai k -toukka, ts. yksi kahdesta erityisestä k - puulajista. K - puu on sointugraafi , jossa on täsmälleen n − k maksimiklikkiä , joista jokainen sisältää k + 1 kärkeä. K -puussa, joka ei itse ole ( k + 1)-klikki , jokainen maksimiklikki joko jakaa graafin kahdeksi tai useammaksi komponentiksi tai sisältää yhden lehtipisteen, kärjen, joka kuuluu vain yhdelle maksimaaliselle klikkille. K -polku on k - puu, jossa on enintään kaksi lehteä, ja k -toukka on k - puu, joka voidaan jakaa k -poluksi ja joukoksi k -lehtiä , joista jokainen on k-klikin erottimen vieressä. k - polusta . Erityisesti polun leveyden yksi maksimikaaviot ovat täsmälleen toukkakäyriä [19] .

Koska polkujaottelut ovat puun hajoamisen erikoistapauksia, minkä tahansa graafin polun leveys on suurempi tai yhtä suuri kuin sen puun leveys . Reitin leveys on myös pienempi tai yhtä suuri kuin leikkausleveys, minimimäärä reunoja, jotka leikkaavat minkä tahansa leikkauksen sellaisten kärkien välillä, joilla on pienempi ja korkeampi indeksi graafin kärkien optimaalisessa lineaarisessa järjestyksessä. Tämä johtuu siitä tosiasiasta, että kärjen jaon suuruus, pienempien indeksien omaavien pisteiden lukumäärä korkeamman indeksin naapureiden kanssa, ei ole suurempi kuin leikkaussärmien lukumäärä [20] [21] . Samasta syystä leikkausleveys ei ylitä polun leveyttä kerrottuna pisteiden maksimiasteella annetussa graafissa [22] [23] .

Minkä tahansa metsän , jolla on n kärkeä, polun leveys on O(log  n ) [24] [25] [26] . Metsästä löytyy aina vakiomäärä pisteitä, joiden poistamisen tuloksena syntyy metsä, joka voidaan jakaa kahdeksi pienemmäksi metsäksi, joissa kussakin on enintään 2 n /3 kärkeä. Lineaarisella järjestyksellä, joka muodostetaan käyttämällä rekursiivisesti tällaista osiota, on kärkien logaritminen hakunumero. Samaa tekniikkaa sovellettaessa graafin puuhajotteluun osoittaa, että jos n -pisteisen graafin G puun leveys on t , niin G :n polun leveys on O( t  log  n ) [27] [28] . Koska ulkotasokaavioilla , rinnakkaissarjakuvaajilla ja Halin- kaavioilla on kaikilla rajoitettu puunleveys, niillä kaikilla on suurin logaritminen polun leveys.

Sen lisäksi, että polun leveys liittyy puunleveyteen, se liittyy napsautusleveyteen ja leikkausleveyteen viivakaavioiden avulla . Graafin G viivagraafilla L ( G ) on kärki G :n jokaiselle reunalle ja kaksi pistettä L ( G ) ovat vierekkäisiä, jos vastaavilla kahdella reunalla on G yhteistä päätepistettä. Kaikilla graafiperheillä on rajattu polunleveys silloin ja vain, jos sen viivakaavioilla on rajattu lineaarinen klikkin leveys, missä lineaarinen klikin leveys korvaa liitosoperaation klikkin leveyden määritelmässä operaatiolla, jolla liitetään yksi uusi kärki [29] . Jos yhdistetyllä graafilla, jossa on kolme tai useampia huippuja, on maksimiaste 3, sen leikkausleveys on yhtä suuri kuin sen viivagraafin kärkijako [30] .

Missä tahansa tasograafissa polun leveys on pahimmassa tapauksessa verrannollinen pisteiden lukumäärän neliöjuureen [31] . Yksi tapa löytää polun hajottelu tällä leveydellä on (samanlainen kuin yllä kuvattu log-leveyden polun hajottelu) käyttää tasomaista osiointilausetta löytääkseen joukko O(√ n ) -pisteitä, joiden poistaminen jakaa graafin kahdeksi aligraafiksi. enintään 2 n /3 kärkeä kussakin, ja yhdistä näille kahdelle aligraafille rekursiivisesti muodostetut polkuhajotteet. Sama tekniikka pätee kaikkiin graafiluokkiin, joille pätee samanlainen osiointilause [32] . Koska millä tahansa graafiperheellä, joka on suljettu alaikäisten ottamiseen, kuten tasograafien tapauksessa, on halkaiseva kärkijoukko, jonka koko on O(√ n ) [33] , tästä seuraa, että minkä tahansa alaikäisten kiinteän perheen graafien polun leveys on jälleen O(√ n ). Joissakin tasograafien luokissa graafin polun leveyden ja sen kaksoisgraafin polun leveyden on oltava välissä, jonka rajat riippuvat lineaarisesti arvoista – tällaiset rajat tunnetaan kaksinkertaisesti kytketyille tasograafisille [34] [35] ja polytoopille. kaavioita [36] [37] . Kaksoisliitetyillä tasokaavioilla kaksoisgraafin polun leveys on pienempi kuin viivakuvaajan polunleveys [38] . Jää avoimeksi kysymykseksi, ovatko tasograafin ja sen duaalin polun leveydet aina lineaarisilla rajoilla muissa tapauksissa.

Joillekin graafiluokille on osoitettu, että polunleveys ja puunleveys ovat aina yhtä suuret toistensa kanssa - tämä pätee kografeihin [39] , permutaatiokaavioihin [40] , vertailukelpoisuuskaavioiden komplementteihin [41] ja intervallijärjestyksen vertailukaavioihin [42] .

Missä tahansa kuutiograafissa tai yleisemmin missä tahansa graafissa, jonka huippupisteaste on 3, polun leveys on enintään n /6 + o( n ), missä n on graafin kärkien lukumäärä. On olemassa kuutiokaavioita, joiden polun leveys on 0,082 n , mutta ei tiedetä, kuinka tämä aukko alarajan ja ylärajan n /6 välillä saadaan umpeen [43] .

Polkujaottelujen laskeminen

Sen määrittäminen, ylittääkö polun leveys tietyn arvon k tietylle graafille, on NP-täydellinen , jos k on syöte [6] . Tunnetuimmat aikarajat ( pahimmassa tapauksessa ) mielivaltaisen n pisteen graafin polunleveyden laskemiseen ovat O(2 n  n c ) jollekin vakiolle c [44] . Joidenkin polun hajottelualgoritmien tiedetään kuitenkin olevan tehokkaampia, jos polun leveys on pieni, jos syötekuvaajaluokka on rajoitettu tai jos polun leveys on arvioitava.

Kiinteäparametrinen ratkaistavuus

Reitin leveys on kiinteä-parametrisesti ratkaistava — mille tahansa vakiolle k voidaan tarkistaa, ylittääkö polun leveys k , ja jos ei, löytää leveyden k polkujako lineaarisessa ajassa [8] . Yleensä nämä algoritmit toimivat kahdessa vaiheessa. Ensimmäinen vaihe käyttää oletusta, että kuvaajan polun leveys k löytää polun tai puuhajotelma. Tämä hajoaminen ei ole optimaalinen, mutta sen leveyttä voidaan rajoittaa k funktiolla . Toisessa vaiheessa käytetään dynaamista ohjelmointialgoritmia optimaalisen hajotuksen löytämiseksi. Tämän tyyppisten tunnettujen algoritmien aikarajat ovat kuitenkin eksponentiaalisia k 2 :ssa , eikä niillä ole käytännön merkitystä, lukuun ottamatta ehkä pieniä k :n arvoja [45] . Tapaukselle k  = 2 Fleiter antoi lineaarisen aika-algoritmin, joka perustuu graafien rakenteelliseen hajotukseen, jonka polunleveys on 2 [46] .

Graafeiden erikoisluokat

Bodlaender [9] antoi yleiskatsauksen polunleveysongelmien monimutkaisuudesta erilaisissa graafien erikoisluokissa. Sen määrittäminen, ylittääkö graafin G polun leveys k :n, jää NP-täydelliseksi ongelmaksi, jos G otetaan rajallisen asteen graafista [47] , tasograafista [47] , rajallisen asteen tasograafista [47] , sointugraafista [48] , sointudominot [49] , vertailtavien graafien komplementit [41] ja kaksiosaiset etäisyyden periytyneet graafit [50] . Tämä viittaa välittömästi siihen, että ongelma on myös NP-täydellinen graafiperheille, jotka sisältävät kaksiosaisia ​​etäisyyden periytyviä kaavioita , mukaan lukien kaksiosaiset graafit, sointujen kaksiosaiset graafit, etäisyyden periytyneet graafit ja ympyräkuvaajat [50] .

Reitin leveys voidaan kuitenkin laskea lineaarisessa ajassa puille ja metsille [10] . Tämä arvo on mahdollista laskea polynomiajassa graafisille, joiden puun leveys on rajattu ja jotka sisältävät rinnakkaiset peräkkäiset graafit , ulkotasograafit ja Halin-graafit [8] sekä jaetut graafit [51] [48] , sointukaavioiden komplementit [ 52] , permutaatiokaaviot [40] , cographs [39] , ympyräkaaren graafit [53] , intervallijärjestyksen vertailukaaviot [42] ja tietysti itse intervallikaaviot , koska niille polun leveys on yksinkertaisesti yhden pienempi kuin maksimivälin peitto minkä tahansa pisteen numero intervalliesityskaaviossa.

Approksimaatioalgoritmit

NP-kova ongelma on graafin polunleveyden approksimaatio additiivisella vakiolla [7] . Tunnetuin polunleveyden polynomiajan approksimaatioalgoritmien approksimaatiokerroin on O((log  n ) 3/2 ) [54] . Varhaiset polunleveyden approksimaatioalgoritmit löytyvät julkaisuista Bodlaender, Gilbert, Hafsteinsson, Klox [7] ja Gooh [55] . Katso rajoitettujen graafiluokkien likiarvo Cloxin ja Bodlaenderin kirjasta [51] .

Laske alaikäiset

Graafin G molli on toinen graafi, joka muodostetaan G :stä supistamalla reunoja, poistamalla reunoja ja pisteitä. Graafi-alaikäisillä on syvä teoria, jossa jotkin tärkeät tulokset käyttävät polunleveyttä.

Metsän poissulkeminen

Jos graafien perhe F suljetaan alaikäisten ottamisen operaatiossa (mikä tahansa perheen F jäsenen alaikäinen sisältyy myös F : een ), niin Robertson–Seymour-lauseen perusteella perhettä F voidaan luonnehtia graafeiksi, jotka eivät sisältävät alaikäisiä X :stä , jossa X on rajallinen joukko kiellettyjä alaikäisiä [56] . Esimerkiksi Wagnerin lause sanoo, että tasograafit ovat graafeja, jotka eivät sisällä koko graafia K 5 eikä täydellistä kaksiosaista graafia K 3,3 sivuina. Monissa tapauksissa F :n ominaisuudet ja X :n ominaisuudet liittyvät läheisesti toisiinsa, ja ensimmäisen tämän tyyppisen tuloksen saivat Robertson ja Seymour [2] ja se yhdistää rajatun polun leveyden olemassaolon metsän olemassaoloon. kiellettyjen alaikäisten perhe. Tarkemmin sanottuna määrittelemme graafiperheen F rajallisen polunleveyden omaavaksi, jos on olemassa vakio p siten, että minkä tahansa F :n graafin polunleveys on enintään p . Silloin alaikäisellä suljetulla perheellä F on rajattu polunleveys silloin ja vain, jos F :n kiellettyjen alaikäisten joukko X sisältää vähintään yhden metsän.

Yhdessä suunnassa tämä tulos voidaan todistaa suoraan – nimittäin, että jos X ei sisällä ainakaan yhtä metsää, niin X -minor-vapaalla graafilla ei ole rajattua polunleveyttä. Tässä tapauksessa X -minorittomat graafit sisältävät kaikki metsät ja erityisesti täydelliset binääripuut . Mutta täydellisillä binääripuilla, joilla on 2k  + 1 taso, on polunleveys k , joten tässä tapauksessa X -minor-vapaiden graafien polunleveys on rajoittamaton. Päinvastaisessa suunnassa, jos X sisältää metsän, jossa on n kärkeä , niin X -minor-vapaiden graafien polun leveys on enintään n  − 2 [57] [58] [59] .

Raideleveysarviot

Ominaisuus, jonka mukaan polun leveys on korkeintaan p , on itsessään vähäinen suljettu ominaisuus – jos G :llä on polun hajotus, jonka leveys on enintään p , niin sama polkuhajotelma pysyy voimassa, jos myös G : stä poistetaan jokin reuna . Kuten mikä tahansa kärkipiste voidaan poistaa G :stä ja sen polun hajotelmasta lisäämättä leveyttä. Reunan kutistuminen voidaan myös suorittaa ilman hajotuksen leveyden lisäämistä yhdistämällä supistettavan reunan kahta päätä edustavat osareitit. Siten graafit, joiden polunleveys on enintään p , voidaan luonnehtia kiellettyjen alaikäisten joukolla X p [56] [16] [60] [61] .

Vaikka X p sisältää välttämättä vähintään yhden metsän, ei ole totta, että kaikki X p :n kuvaajat ovat metsiä. Esimerkiksi X 1 koostuu kahdesta graafista, puusta, jossa on seitsemän kärkeä, ja kolmiosta K 3 . X p :n puiden joukko voidaan kuitenkin kuvata tarkasti - nämä ovat juuri niitä puita, jotka voidaan muodostaa kolmesta puusta X p  − 1 :stä muodostamalla uusi juuri ja yhdistämällä se reunoilla mielivaltaisesti valittuihin pienempien puiden kärkipisteisiin. Esimerkiksi puu, jossa on seitsemän kärkeä X 1 :ssä , muodostetaan puista, joissa on kaksi kärkeä (yksi reuna) X 0 :sta . Tämän konstruktion perusteella voidaan osoittaa, että kiellettyjen alaikäisten määrä X p :ssä ei ole pienempi kuin ( p !) 2 [16] [60] [61] . Kiellettyjen alaikäisten täydellinen joukko X 2 kaavioille, joiden polunleveys on 2, on laskettu. Tämä sarja sisältää 110 erilaista kuvaajaa [62] .

Rakenneteoria

Graafisen rakennelauseen pienimuotoisten suljettujen graafien perheille väitetään, että jokaiselle perheelle F , jossa graafit voidaan hajottaa klikkisummuiksi, graafit, jotka voidaan upottaa rajatun suvun pintoihin sekä rajattu määrä pisteitä ja pyörteitä, kullekin. Klikkisumman komponentti. Huippupiste on piste, joka on komponentin kaikkien kärkien vieressä, ja pyörre on rajatun polun leveyden kuvaaja, joka on liimattu komponentin pinnalle rajatun suvun injektiolla. Pyörteen sisäkkäisen pinnan ympärillä olevien kärkien syklisen järjestyksen on oltava yhteensopiva pyörteen puuhajoamisen kanssa siinä mielessä, että syklin katkaiseminen lineaarisen järjestyksen muodostamiseksi täytyy johtaa järjestykseen, jossa on rajoitettu määrä pyörteiden erotusta [ 5] . Tällä teorialla, jossa polunleveys liittyy läheisesti mielivaltaisiin alaikäisten graafien perheisiin, on tärkeä algoritminen sovellus [63] .

Sovellukset

VLSI

VLSI : n kehittämisen aikana pisteiden jakamisen ongelmaa tutkittiin alun perin keinona jakaa ketjuja pienempiin alijärjestelmiin, joissa on pieni määrä komponentteja järjestelmien välisellä rajalla [47] .

Otsuki, Mori, Kuh ja Kashiwabara [64] käyttivät intervallin paksuutta mallintaakseen tarvittavien johtimien lukumäärän VLSI-piirien yksiulotteisessa järjestelyssä, joka muodostuu useista verkkojärjestelmään yhdistettävistä moduuleista. Heidän mallissaan voidaan muodostaa graafi, jossa kärjet edustavat ketjuja ja jossa kaksi kärkeä on yhdistetty reunalla, jos niiden ketjut on kytketty samaan moduuliin. Eli jos moduulit ja ketjut ymmärretään hypergraafin kärkeiksi ja hyperreunuksiksi , niin niistä muodostettu graafi on hypergraafin viivakaavio . Tämän viivakaavion supergraafin intervalliesitys yhdessä supergraafin värityksen kanssa kuvaa verkkojen sijoittelua vaakasuorille raiteille (yksi raita kutakin väriä kohden), jotta moduulit voidaan järjestää raitoja pitkin lineaarisessa järjestyksessä ja yhdistää halutut verkot. Siitä tosiasiasta, että intervallikaaviot ovat täydellisiä [65] , seuraa, että tämän tyyppiseen optimaaliseen asetteluun tarvittava värien määrä on yhtä suuri kuin ketjukaavion intervallikomplementin klikkiluku.

Kytkinmatriisin pinoaminen [66] on erityinen CMOS VLSI-pinoaminen logiikkaalgebrapiireille . Kytkimien matriisipinoamisessa signaali etenee "linjoja" (pystysegmenttejä) pitkin, kun taas kukin kytkin muodostuu vaakasuuntaisella segmentillä sijaitsevista elementeistä. Siten kunkin kytkimen vaakasuuntaisten segmenttien on leikattava pystysuorat segmentit jokaisella kytkimen tulona tai lähtönä toimivalla viivalla. Kuten Otsuki-, Mori-, Kuha- ja Kashiwabara-pinouksissa [64] , tämän tyyppinen pinoaminen, joka minimoi pystysuorien viivojen määrän, voidaan laskea laskemalla graafin polunleveys, jossa on viivoja kärkeinä ja rivipari, jotka kuuluvat kytkin reunana [67 ] . Samaa algoritmista lähestymistapaa voidaan käyttää myös ohjelmoitavien logiikkapiirien pinoamisongelmien mallintamiseen [68] [69] .

Kuvaajan visualisointi

Pathwidthillä on useita kaavioiden visualisointisovelluksia :

• Minimikaavioilla, joissa on tietty määrä risteyksiä, on polunleveys, jota rajoittaa leikkauspisteiden lukumäärä [70] .
• Niiden rinnakkaisten viivojen määrä, joille puun kärjet voidaan sijoittaa risteämättä reunoja (erilaisten luonnollisten rajoitusten alaisena tavalle, jolla vierekkäiset kärjet voidaan sijoittaa viivoille, joilla on rivijono), on verrannollinen puun polun leveyteen [71] .
• Graafin G k - leikkautunut h -tason piirustus on graafin G kärkien järjestely h:lle ​​eri vaakaviivalle, joiden reunat ovat yksivärisiä (esitetty katkoviivoilla) viivojen välisiä polkuja, joissa on useimmat k risteyksiä. Tällä esityksellä varustetuilla kaavioilla on reitin leveys, jota rajoittaa h :n ja k :n funktio . Siten, jos h :n ja k :n arvot ovat vakioita, voidaan lineaarisessa ajassa määrittää, onko kaaviossa k -ristitetty h - tason piirros [72] .
• Graafi, jossa on n kärkeä ja polun leveys p , voidaan upottaa kolmiulotteiseen hilaan, jonka koko on p × p × n , siten, että kaksi reunaa (jota edustavat hilapisteiden väliset suorat janat) eivät leikkaa toisiaan. Siten rajatun polunleveyden kaavioissa on tämän tyyppisiä upotuksia lineaarisella tilavuudella [73] .

Kääntäjän suunnittelu

Korkean tason ohjelmointikieliä käännettäessä syntyy polunleveys ongelmassa lineaarisen koodin (eli koodi ilman ohjauslogiikkaa - siirtymät ja silmukat) uudelleenjärjestämistä siten, että kaikki koodissa lasketut arvot voivat olla konerekistereissä , ja ei pakotettu pois päämuistiin. Tässä sovelluksessa käännetty koodi esitetään suunnattuna asyklisenä graafina (DAG), jossa kärjet edustavat koodin syötearvoja ja koodin sisällä suoritettujen toimintojen tuloksena laskettuja arvoja. Reuna solmusta x solmuun y tässä NAG:ssa edustaa sitä tosiasiaa, että arvo x on yksi operaation y syötteistä . Tämän NAG:n kärkien topologinen lajittelu edustaa koodin oikeaa lajittelua, ja koodin suorittamiseen tässä järjestyksessä tarvittavien rekisterien lukumäärä saadaan järjestyksen kärkijaosta [74] .

Jokaiselle koneen kiinteälle määrälle w rekistereitä voidaan lineaarisessa ajassa määrittää, voidaanko lineaarisen koodin pala järjestää uudelleen siten, että koodi vaatii enintään w rekisteriä. Jos topologisen järjestyksen kärkierotus on korkeintaan w , ei kaikkien järjestysten välinen huippupisteerotus voi olla suurempi, joten suuntaamattomien graafien, jotka on muodostettu jättämällä huomioimatta edellä kuvatun NAG:n orientaatio, polun leveyden tulee olla enintään w . Voidaan tarkistaa, onko tämä totta tunnetuilla kiinteän parametrin määritettävillä polunleveysalgoritmeilla, ja jos se on totta, löytää polun hajotelma suuntaamattomille kuvaajille lineaarisessa ajassa olettaen, että w on vakio. Kun puun jakautuminen on löydetty, topologinen järjestys leveydellä w (jos sellainen on) voidaan löytää dynaamisen ohjelmoinnin avulla, jälleen lineaarisessa ajassa [74] .

Kielitiede

Karnai ja Tutsa [75] kuvasivat polunleveyden soveltamista luonnollisen kielen käsittelyyn . Tässä sovelluksessa lauseet mallinnetaan kaavioina, joissa kärjet edustavat sanoja ja reunat sanojen välisiä suhteita. Jos esimerkiksi adjektiivi muokkaa substantiivia, kaaviossa on reuna näiden kahden sanan välillä. Ihmisen lyhytaikaisen muistin rajallisen kapasiteetin vuoksi Miller [76] , Kornai ja Tutsa väittävät, että tällä kaaviolla on oltava rajoitettu polunleveys (tarkemmin sanottuna, he väittävät, että tämä polun leveys ei ylitä kuutta), muuten ihmiset eivät pystyisi tunnistamaan puheen oikein.

Eksponentiaaliset algoritmit

Monet graafiteorian ongelmat voidaan ratkaista tehokkaasti graafisilla, joilla on pieni polunleveys dynaamisen ohjelmoinnin avulla , joka perustuu graafin polun hajotteluun [11] . Esimerkiksi, jos graafin G , jossa on n pistettä, kärkien lineaarinen järjestys on annettu ja pisteen erotusarvo on yhtä suuri kuin w , niin on mahdollista löytää graafin G suurin itsenäinen joukko kaavalla O(2 w n ) aika [43] . Graafilla, jolla on rajoitettu polunleveys, tämä lähestymistapa johtaa kiinteäparametrisesti päätettävissä oleviin polunleveysparametrisoituihin algoritmeihin [67] . Tällaisia ​​tuloksia ei usein löydy kirjallisuudesta, koska ne kuuluvat samanlaisten puunleveysparametrisoitujen algoritmien ryhmään. Kuitenkin polunleveys näkyy jopa puunleveyteen perustuvissa dynaamisissa ohjelmointialgoritmeissa, kun mitataan näiden algoritmien kapasiteetin monimutkaisuutta [12] .

Samaa dynaamista ohjelmointitekniikkaa voidaan soveltaa kuvaajiin, joilla on rajoittamaton polunleveys, mikä johtaa algoritmeihin, jotka ratkaisevat kaavioiden parametroimattomia ongelmia eksponentiaalisessa ajassa . Esimerkiksi dynaamisen ohjelmoinnin yhdistäminen siihen tosiasiaan, että kuutiograafien polunleveys on n /6 + o( n ), osoittaa, että kuutiograafille voidaan rakentaa suurin riippumaton joukko O(2 n /6 + o( n ) ) aika, joka on nopeampi kuin aiemmin tunnetut menetelmät [43] . Samankaltainen lähestymistapa johtaa parannettuihin eksponentiaalisen aika-algoritmeihin maksimileikkauksen ja minimidominoivan joukko -ongelmille kuutiokaavioille [43] ja joihinkin muihin NP-koviin optimointiongelmiin [77] [78] .

Katso myös

• Intervallikuvaajan ulottuvuus , toinen tapa mitata mielivaltaisten kaavioiden monimutkaisuutta intervallikaavioina
• Puun syvyys , luku, joka on rajoitettu pienille suljetuille graafiperheille, jos ja vain jos perhe ei sisällä polkua
• Degeneraatio , graafin harveuden mitta , joka ei ole suurempi kuin graafin polun leveys
• Kuvaajan nauhan leveys , toinen NP-täydellinen optimointiongelma lineaaristen graafien pinoamista käyttäen
• Strahlerin luku , juurtuneiden puiden tiheyden mitta, joka määritellään samalla tavalla kuin suuntaamattomien puiden polun leveys

Muistiinpanot

1. ↑ Diestel, Kühn, 2005 .
2. ↑ 1 2 3 4 5 Robertson, Seymour, 1983 .
3. ↑ 1 2 Bodlaender, 1998 .
4. ↑ Monet artikkelissa käytetyistä termeistä löytyvät F. V. Fominin väitöskirjan johdannosta (( Fomin 1996 ))
5. ↑ 12 Robertson , Seymour, 2003 .
6. ↑ 1 2 Kashiwabara, Fujisawa, 1979 ; Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979 ; Lengauer 1981 ; Arnborg, Corneil, Proskurowski, 1987 .
7. ↑ 1 2 3 Bodlaender, Gilbert, Hafsteinsson, Kloks, 1992 .
8. ↑ 1 2 3 Bodlaender (1996 ); Bodlaender, Kloks (1996 )
9. ↑ 1 2 Bodlaender, 1994 .
10. ↑ 12 Möhring , 1990 ; Scheffler, 1990 ; Ellis, Sudborough, Turner, 1994 ; Coudert, Huc, Mazauric, 1998 ; Peng, Ho, Hsu, Ko, Tang, 1998 ; Skodinis, 2000 ; Skodinis (2003 ).
11. ↑ 12 Arnborg , 1985 .
12. ↑ 1 2 Aspvall, Proskurowski, Telle, 2000 .
13. ↑ Bodlaender, 1994 , s. 1–2.
14. ↑ Bodlaender, 1998 , s. 13, Lause 29.
15. ↑ Ellis, Sudborough, Turner, 1983 .
16. ↑ 1 2 3 Kinnersley, 1992 .
17. ↑ Bodlaender, 1998 , s. Lause 51.
18. ↑ Kirousis, Papadimitriou, 1985 .
19. ↑ Proskurowski, Telle, 1999 .
20. ↑ Korach, Solel, 1993 , s. 99, Lemma 3.
21. ↑ Bodlaender, 1998 , s. 24, Lause 47.
22. ↑ Korach, Solel, 1993 , s. 99, Lemma 1.
23. ↑ Bodlaender, 1998 , s. 24, Lause 49.
24. ↑ Korach, Solel, 1993 , s. 99, Lause 5.
25. ↑ Bodlaender, 1998 , s. 30, Lause 66.
26. ↑ Scheffler (1992 ) antaa vahvemman rajan n - vertexin metsän log 3 (2 n  + 1) polun leveydelle .
27. ↑ Korach, Solel, 1993 , s. 100, Lause 6.
28. ↑ Bodlaender, 1998 , s. 10, seuraus 24.
29. ↑ Gurski, Wanke, 2007 .
30. ↑ Golovach, 1993 .
31. ↑ Bodlaender, 1998 , s. 10, seuraus 23.
32. ↑ Bodlaender, 1998 , s. 9, Lause 20.
33. ↑ Alon, Seymour, Thomas, 1990 .
34. ↑ Bodlaender, Fomin, 2002 .
35. ↑ Coudert, Huc, Sereni, 2007 .
36. ↑ Fomin, Thilikos, 2007 .
37. ↑ Amini, Huc, Perennes, 2009 .
38. ↑ Fomin, 2003 .
39. ↑ 1 2 Bodlaender, Möhring, 1990 .
40. ↑ 1 2 Bodlaender, Kloks, Kratsch, 1993 .
41. ↑ 1 2 Habib, Möhring, 1994 .
42. ↑ 12 Garbe , 1995 .
43. ↑ 1 2 3 4 Fomin, Høie, 2006 .
44. ↑ Fomin, Kratsch, Todinca, Villanger, 2008 .
45. ↑ Downey, Fellows, 1999 , s. 12.
46. ↑ de Fluiter, 1997 .
47. ↑ 1 2 3 4 Monien, Sudborough, 1988 .
48. ↑ 12. Gusted , 1993 .
49. ↑ Kloks, Kratsch, Müller, 1995 . Sointudomino on sointukaavio, jossa mikä tahansa kärki kuuluu korkeintaan kahteen maksimiklikkiin
50. ↑ 1 2 Kloks, Bodlaender, Müller, Kratsch, 1993 .
51. ↑ 1 2 Kloks, Bodlaender, 1992 .
52. ↑ Garbe (1995 ) pitää tämän tuloksen Ton Cloxin vuoden 1993 väitöskirjan ansioksi. Garben polynomiaikaalgoritmi intervallijärjestyksen vertailukelpoisille kaavioille yleistää tämän tuloksen, koska minkä tahansa sointugraafin on oltava tämän tyyppinen vertailukäyrä.
53. ↑ Suchan, Todinca, 2007 .
54. ↑ Feige, Hajiaghayi, Lee, 2005 .
55. ↑ Guha, 2000 .
56. ↑ 12 Robertson , Seymour, 2004 .
57. ↑ Bienstock, Robertson, Seymour, Thomas, 1991 .
58. ↑ Diestel, 1995 .
59. ↑ Cattell, Dinneen, Fellows, 1996 .
60. ↑ 1 2 Takahashi, Ueno, Kajitani, 1994 .
61. ↑ 1 2 Bodlaender, 1998 , s. kahdeksan.
62. ↑ Kinnersley, Langston, 1994 .
63. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2005 .
64. ↑ 1 2 Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979 .
65. ↑ Berge, 1967 .
66. ↑ Lopez, laki, 1980 .
67. ↑ 12 Fellows , Langston, 1989 .
68. ↑ Möhring, 1990 .
69. ↑ Ferreira, laulu, 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 .

Kirjallisuus

• Noga Alon, Paul Seymour, Robin Thomas. Proc. 22. ACM Symp. Tietojenkäsittelyteoriasta (STOC 1990) . - 1990. - S.  293 -299. — ISBN 0897913612 . - doi : 10.1145/100216.100254 . .
• Omid Amini, Florian Huc, Stephane Perennes. Tasograafien polun leveydestä // SIAM Journal on Discrete Mathematics . - 2009. - T. 23 , no. 3 . - S. 1311-1316 . - doi : 10.1137/060670146 . .
• Stefan Arnborg. Tehokkaat algoritmit kombinatorisiin ongelmiin rajoitetulla hajotettavuudella varustetuissa kaavioissa – Tutkimus // BIT. - 1985. - T. 25 , no. 1 . - S. 2-23 . - doi : 10.1007/BF01934985 . .
• Stefan Arnborg, Derek G. Corneil, Andrzej Proskurowski. $k$-puun upotusten löytämisen monimutkaisuus // SIAM Journal on Algebraic and Discrete Methods. - 1987. - T. 8 , no. 2 . - S. 277-284 . - doi : 10.1137/0608024 . .
• Bengt Aspvall, Andrzej Proskurowski, Jan Arne Telle. Muistivaatimukset taulukkolaskutoimille osittaisissa k - puualgoritmeissa // Algorithmica . - 2000. - T. 27 , no. 3 . - S. 382-394 . - doi : 10.1007/s004530010025 . .
• Claude Berge. Graafiteoria ja teoreettinen fysiikka. - New York: Academic Press, 1967. - S. 155-165. .
• .
• Andreas Björklund, Thore Husfeldt. Tarkat algoritmit tarkan tyydyttävyyden ja täydellisten vastaavuuksien lukumäärään // Algorithmica . - 2008. - T. 52 , no. 2 . - S. 226-249 . - doi : 10.1007/s00453-007-9149-8 . .
• Hans L. Bodlaender. Turistiopas läpi puun leveyden // Acta Cybernetica. - 1994. - T. 11 .
• Hans L. Bodlaender. Tietojenkäsittelyteorian kehitys (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16.–20.11.1992) / Jürgen Dassow, Alisa Kelemenová. - Gordon and Breach, 1994. - V. 6. - S. 1-20. - (Tietokonematematiikan aiheita). .
• Hans L. Bodlaender. Lineaariaikainen algoritmi pienen puunleveyden puuhajotelmien etsimiseen // SIAM Journal on Computing . - 1996. - T. 25 , no. 6 . - S. 1305-1317 . - doi : 10.1137/S0097539793251219 . .
• Hans L. Bodlaender. Graafeiden osittainen k -arboretum rajoitetulla puunleveydellä  //  Tietojenkäsittelyteoria. - 1998. - Voi. 209 , iss. 1-2 . - s. 1-45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
• Hans L. Bodlaender, Fedor V. Fomin. Ulompitasoisten graafien polunleveyden likimääräisyys // Journal of Algorithms. - 2002. - T. 43 , no. 2 . - S. 190-200 . - doi : 10.1016/S0196-6774(02)00001-9 . .
• Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, Ton Kloks. Tietojenkäsittelytieteen graafiteoreettiset käsitteet. - 1992. - T. 570. - S. 1-12. — ( Tietojenkäsittelytieteen luentomuistiinpanot ). - ISBN 978-3-540-55121-8 . - doi : 10.1007/3-540-55121-2_1 . .
• Hans L. Bodlaender, Jens Gustedt, Jan Arne Telle. Proc. 9. ACM–SIAM-symposium diskreetistä algoritmista (SODA '98). - 1998. - S. 574-583. .
• Hans L. Bodlaender, Ton Kloks. Tehokkaat ja rakentavat algoritmit graafien polun ja puun leveydelle // Journal of Algorithms. - 1996. - T. 21 , no. 2 . - S. 358-402 . - doi : 10.1006/jagm.1996.0049 . .
• Hans L. Bodlaender, Ton Kloks, Dieter Kratsch. Proc. 20. kansainvälinen kollokviumi automaateista, kielistä ja ohjelmoinnista (ICALP 1993) . - Springer-Verlag, 1993. - T. 700. - S. 114-125. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-56939-8 . - doi : 10.1007/3-540-56939-1_66 . .
• Hans L. Bodlaender, Rolf H. Möhring. Proc. 2nd Scandinavian Workshop on Algorithm Theory . - Springer-Verlag, 1990. - T. 447. - S. 301-309. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-52846-3 . - doi : 10.1007/3-540-52846-6_99 . .
• Kevin Cattell, Michael J. Dinneen, Michael R. Fellows. Yksinkertainen lineaarinen aikaalgoritmi pienen leveyden polkuhajotelmien etsimiseen // Information Processing Letters . - 1996. - T. 57 , no. 4 . - S. 197-203 . - doi : 10.1016/0020-0190(95)00190-5 . .
• David Coudert, Florian Huc, Dorian Mazauric. Proc. 22nd Int. Symp. hajautettua laskentaa. - Springer-Verlag, 1998. - T. 5218. - S. 500-501. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - ISBN 978-3-540-87778-3 . - doi : 10.1007/978-3-540-87779-0_36 . .
• David Coudert, Florian Huc, Jean-Sébastien Sereni. Ulompitasoisten graafien polunleveys // Journal of Graph Theory . - 2007. - T. 55 , no. 1 . - S. 27-41 . - doi : 10.1002/jgt.20218 . .
• Reinhard Diestel. Graph Minors I: lyhyt todistus polunleveyslauseesta // Kombinatoriikka, todennäköisyys ja laskeminen . - 1995. - T. 4 , no. 1 . - S. 27-30 . - doi : 10.1017/S0963548300001450 . .
• Reinhard Diestel, Daniela Kühn. Piirrä sivuhierarkiat // Diskreetti sovellettu matematiikka . - 2005. - T. 145 , no. 2 . - S. 167-182 . - doi : 10.1016/j.dam.2004.01.010 . .
• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi. Proc. 46. ​​IEEE-symposiumi tietojenkäsittelytieteen perusteista (FOCS 2005) . - 2005. - S. 637-646. — ISBN 0-7695-2468-0 . - doi : 10.1109/SFCS.2005.14 . .
• Rod G. Downey, Michael R. Fellows. Parametrisoitu monimutkaisuus. - Springer-Verlag, 1999. - ISBN 0-387-94883-X . .
• V. Dujmović, M. R. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, S. Whitesides, David R. Wood. Kerrosteisen graafin piirtämisen parametroidusta monimutkaisuudesta // Algorithmica . - 2008. - T. 52 , no. 2 . - S. 267-292 . - doi : 10.1007/s00453-007-9151-1 . .
• Vida Dujmovic, Pat Morin, David R. Wood. Proc. 10. kansainvälinen grafiikkapiirustuksen symposium (GD 2002) . - Springer-Verlag, 2003. - T. 2528. - S. 42-53. — (Luentomuistiinpanot tietojenkäsittelytieteestä). .
• JA Ellis, IH Sudborough, JS Turner. Proc. 1983 Allerton Conf. viestinnästä, ohjauksesta ja tietojenkäsittelystä. – 1983 . Monien & Sudborough (1988 ) siteeraamalla.
• JA Ellis, IH Sudborough, JS Turner. Puun kärjen erotus ja hakunumero // Information and Computation . - 1994. - T. 113 , numero. 1 . - S. 50-79 . - doi : 10.1006/inco.1994.1064 . .
• Uriel Feige, Mohammadtaghi Hajiaghayi, James R. Lee. Proc. 37. ACM Symposium on Theory of Computing (STOC 2005) . - 2005. - S. 563-572. — ISBN 1581139608 . - doi : 10.1145/1060590.1060674 . .
• Michael R. Fellows, Michael A. Langston. Proc. 21. ACM Symposium on Theory of Computing . - 1989. - S. 501-512. — ISBN 0897913078 . - doi : 10.1145/73007.73055 . .
• Afonso G. Ferreira, Siang W. Song. Proc. 1. Latinalaisen Amerikan symposium teoreettisesta informatiikasta (LATIN '92). - Springer-Verlag, 1992. - T. 583. - S. 139-153. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 3-540-55284-7 . - doi : 10.1007/BFb0023825 . .
• Babette de Fluiter. Pienen puunleveyden kuvaajien algoritmit . - Utrechtin yliopisto , 1997. - (Ph.D. thesis). — ISBN 90-393-1528-0 . .
• Fedor V. Fomin. Taso- ja viivakaavioiden polunleveys // Grafit ja kombinatoriikka . - 2003. - T. 19 , no. 1 . - S. 91-99 . - doi : 10.1007/s00373-002-0490-z . .
• Fedor V. Fomin, Kjartan Hoie. Kuutiokaavioiden polunleveys ja tarkat algoritmit // Tietojenkäsittelykirjaimet . - 2006. - T. 97 , no. 5 . - S. 191-196 . - doi : 10.1016/j.ipl.2005.10.012 . .
• Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, Yngve Villanger. Tarkat algoritmit puunleveydelle ja minimitäytölle // SIAM Journal on Computing . - 2008. - T. 38 , no. 3 . - S. 1058-1079 . - doi : 10.1137/050643350 . .
• Fedor V. Fomin, Dimitrios M. Thilikos. Polunleveyden itsestään kaksinaisuudesta monitahoisen graafin upotuksessa // Journal of Graph Theory . - 2007. - T. 55 , no. 1 . - S. 42-54 . - doi : 10.1002/jgt.20219 . .
• Renate Garbe. Proc. 20. kansainvälinen työpaja Graafiteoreettiset käsitteet tietojenkäsittelytieteessä (WG'94). - Springer-Verlag, 1995. - T. 903. - S. 26-37. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-59071-2 . - doi : 10.1007/3-540-59071-4_35 . .
• P.A. Golovach. Graafin leveys ja viivakaavion kärjen erotusnumero // Discrete Mathematics and Applications. - 1993. - Osa 3 , numero. 5 . - S. 517-522 . - doi : 10.1515/dma.1993.3.5.517 . .
• Sudipto Guha. Proc. IEEE:n 41. symposiumi tietojenkäsittelytieteen perusteista (FOCS 2000) . - 2000. - s. 126. - ISBN 0-7695-0850-2 . - doi : 10.1109/SFCS.2000.892072 . .
• Frank Gurski, Egon Wanke. Rajoitetun klikinleveyden viivakaaviot // Diskreetti matematiikka . - 2007. - T. 307 , no. 22 . - S. 2734-2754 . - doi : 10.1016/j.disc.2007.01.020 . .
• Jens Gusted. Sointukaavioiden polunleveydestä // Discrete Applied Mathematics . - 1993. - T. 45 , no. 3 . - S. 233-248 . - doi : 10.1016/0166-218X(93)90012-D . .
• Michel Habib, Rolf H. Möhring. Yhteisvertailukaavioiden puuleveys ja uusi järjestysteoreettinen parametri // Järjestys . - 1994. - T. 11 , no. 1 . - S. 47-60 . - doi : 10.1007/BF01462229 . .
• Petr Hlineny. Ristikkäisten lukujen kriittiset kuvaajat ovat rajoittaneet polun leveyttä // Journal of Combinatorial Theory, Series B . - 2003. - T. 88 , no. 2 . - S. 347-367 . - doi : 10.1016/S0095-8956(03)00037-6 . .
• T. Kashiwabara, T. Fujisawa. Proc. Piirejä ja järjestelmiä käsittelevä kansainvälinen symposium . - 1979. - S. 657-660. .
• Nancy G. Kinnersley. Graafin kärkien erotusnumero on yhtä suuri kuin sen polun leveys // Information Processing Letters . - 1992. - T. 42 , no. 6 . - S. 345-350 . - doi : 10.1016/0020-0190(92)90234-M . .
• Nancy G. Kinnersley, Michael A. Langston. Estejoukon eristys porttimatriisiasetteluongelmalle // Discrete Applied Mathematics . - 1994. - T. 54 , no. 2-3 . - S. 169-213 . - doi : 10.1016/0166-218X(94)90021-3 . .
• Lefteris M. Kirousis, Christos H. Papadimitriou. Intervallikaaviot ja haku // Diskreetti matematiikka . - 1985. - T. 55 , no. 2 . - S. 181-184 . - doi : 10.1016/0012-365X(85)90046-9 .  (linkki ei saatavilla) .
• Ton Kloks, Hans L. Bodlaender. Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92). - Springer-Verlag, 1992. - T. 650. - S. 116-125. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-56279-5 . - doi : 10.1007/3-540-56279-6_64 . .
• T. Kloks, H. Bodlaender, H. Müller, D. Kratsch. Proc. 1st European Symposium on Algorithms (ESA'93) . - Springer-Verlag, 1993. - T. 726. - S. 260-271. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/3-540-57273-2_61 . .
• Ton Kloks, Dieter Kratsch, H. Müller. Proc. 20. kansainvälinen työpaja Graafiteoreettiset käsitteet tietojenkäsittelytieteessä (WG'94). - Springer-Verlag, 1995. - T. 903. - S. 106-120. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-59071-2 . - doi : 10.1007/3-540-59071-4_41 . .
• Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith. Proc. 31. kansainvälinen työpaja tietojenkäsittelytieteen graafiteoreettisista käsitteistä (WG 2005). - Springer-Verlag, 2005. - T. 3787. - S. 385-396. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - ISBN 978-3-540-31000-6 . - doi : 10.1007/11604686_34 . .
• Ephraim Korach, Nir Solel. Puun leveys, polun leveys ja leikkausleveys // Discrete Applied Mathematics . - 1993. - T. 43 , no. 1 . - S. 97-101 . - doi : 10.1016/0166-218X(93)90171-J . .
• Andras Kornai, Zsolt Tuza. Kapeaus, polun leveys ja niiden soveltaminen luonnollisen kielen käsittelyyn // Discrete Applied Mathematics . - 1992. - T. 36 , no. 1 . - S. 87-92 . - doi : 10.1016/0166-218X(92)90208-R . .
• Thomas Lengauer. Mustavalkoiset kivet ja kuvaajien erottelu  // Acta Informatica . - 1981. - T. 16 , no. 4 . - S. 465-475 . - doi : 10.1007/BF00264496 . .
• Alexander D. Lopez, Hung-Fai S. Law. Tiheä porttimatriisiasettelumenetelmä MOS VLSI // IEEE Transactions on Electron Devices. - 1980. - T. ED-27 , no. 8 . - S. 1671-1675 . - doi : 10.1109/T-ED.1980.20086 . .
• George A. Miller. Maaginen numero seitsemän, plus tai miinus kaksi // Psykologinen katsaus . - 1956. - T. 63 , no. 2 . - S. 81-97 . - doi : 10.1037/h0043158 . — PMID 13310704 . .
• Rolf H. Möhring. Computational Graph Theory / G. Tinhofer, E. Mayr, H. Noltemeier, M. Sysło. - Springer-Verlag, 1990. - T. 7. - S. 17-51. - (Computing Supplementum). — ISBN 3-211-82177-5 . .
• B. Monien, IH Sudborough. Min leikkaus on NP-täydellinen reunapainotetuille puille  //  Teoreettinen tietojenkäsittelytiede. - 1988. - Voi. 58 , iss. 1-3 . - s. 209-229 . - doi : 10.1016/0304-3975(88)90028-X . .
• Tatsuo Ohtsuki, Hajimu Mori, Ernest S. Kuh, Toshinobu Kashiwabara, Toshio Fujisawa. Yksiulotteinen logiikkaportin määritys ja intervallikaaviot // IEEE Transactions on Circuits and Systems. - 1979. - T. 26 , no. 9 . - S. 675-684 . - doi : 10.1109/TCS.1979.1084695 . .
• Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, Chuan Yi Tang. Proc. 4th Int. Conf. Computing and Combinatoriics (COCOON'98). - Springer-Verlag, 1998. - T. 1449. - S. 197-205. — (Luentomuistiinpanot tietojenkäsittelytieteestä). .
• Andrzej Proskurowski, Jan Arne Telle. Graafiluokat rajoitetuilla intervallimalleilla  //  Teoreettinen tietojenkäsittelytiede. - 1999. - Voi. 3 . - s. 167-176 . .
• Neil Robertson, Paul Seymour. kuvaa alaikäisiä. I. Metsää lukuun ottamatta // Journal of Combinatorial Theory, sarja B . - 1983. - T. 35 , no. 1 . - S. 39-61 . - doi : 10.1016/0095-8956(83)90079-5 . .
• Neil Robertson, Paul Seymour. kuvaa alaikäisiä. XVI. Lukuun ottamatta ei-tasomaista kuvaajaa // Journal of Combinatorial Theory, sarja B . - 2003. - T. 89 , no. 1 . - S. 43-76 . - doi : 10.1016/S0095-8956(03)00042-X . .
• Neil Robertson, Paul D. Seymour. Kaavio alaikäiset. XX. Wagnerin arvelu // Journal of Combinatorial Theory, sarja B . - 2004. - T. 92 , no. 2 . - S. 325-357 . - doi : 10.1016/j.jctb.2004.08.001 . .
• Petra Scheffler. Kombinatorian ja graafisen teorian aiheet / R. Bodendiek, R. Henn. - Physica-Verlag, 1990. - S. 613-620. .
• Petra Scheffler. Neljäs Tšekkoslovakian symposium kombinatoriikasta, graafista ja monimutkaisuudesta / Jaroslav Nešetřil, Miroslav Fiedler. - Elsevier, 1992 .
• Konstantin Skodinis. Proc. 8th European Symposium on Algorithms (ESA 2000) . - Springer-Verlag, 2000. - T. 1879. - S. 403-414. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - ISBN 978-3-540-41004-1 . - doi : 10.1007/3-540-45253-2_37 . .
• Konstantin Skodinis. Lineaaristen puuasettelujen rakentaminen, jotka ovat optimaalisia pisteiden erottelun suhteen lineaarisessa ajassa // Journal of Algorithms. - 2003. - T. 47 , no. 1 . - S. 40-59 . - doi : 10.1016/S0196-6774(02)00225-0 . .
• Karol Suchan, Ioan Todinca. Proc. 33. kansainvälinen työpaja tietojenkäsittelytieteen graafiteoreettisista käsitteistä (WG 2007). - Springer-Verlag, 2007. - T. 4769. - S. 258-269. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/978-3-540-74839-7_25 . .
• Matthew Suderman. Puiden polunleveys ja kerrospiirrokset // International Journal of Computational Geometry and Applications . - 2004. - T. 14 , no. 3 . - S. 203-225 . - doi : 10.1142/S0218195904001433 . Arkistoitu alkuperäisestä 3. toukokuuta 2003. .
• Atsushi Takahashi, Shuichi Ueno, Yoji Kajitani. Minimaaliset asykliset kielletyt alamerkit graafiperheelle, jonka polun leveys on rajoitettu // Diskreetti matematiikka . - 1994. - T. 127 , no. 1-3 . - S. 293-304 . - doi : 10.1016/0012-365X(94)90092-2 . .
• F.V. Fomin. Graafista etsimisen ja etsimisen ongelmat // Electronic Library of Dissertations. – 1996.