Түзу - Treewidth - Wikipedia

Жылы графтар теориясы, кеңдік бағытталмаған графтың - бұл графикамен байланысты сан. Төмен ені бірнеше эквиваленттік жолмен анықталуы мүмкін: а-да орнатылған ең үлкен шыңның мөлшері ағаштың ыдырауы графиктің, ең үлкенінің өлшемі клика ішінде аккордты аяқтау графиктің максимум реті панах а-ға арналған стратегияны сипаттай отырып іздеу-жалтару графиктегі ойын немесе а-ның максималды реті қыңыр, барлығы бір-біріне тиетін байланыстырылған субграфтардың жиынтығы.

Treewidth әдетте параметр ретінде қолданылады параметрленген күрделілік графикті талдау алгоритмдер. Ең үлкен ені бар графиктер к деп те аталады жартылай к- ағаштар; көптеген басқа зерттелген графтар отбасыларының ені шектелген.

Кеңдік ұғымын алғашында Умберто Бертеле және Франческо Бриошки енгізген (1972 ) атымен өлшем. Ол кейінірек қайта ашылды Рудольф Халин (1976 ), басқа графикалық параметрмен бөлісетін қасиеттерге негізделген, Хадвигер нөмірі. Кейінірек ол қайтадан ашылды Нил Робертсон және Пол Сеймур (1984 ) және содан бері көптеген басқа авторлар зерттеген.^[1]

Анықтама

Сегіз төбесі бар график және оның алты түйіні бар ағашқа ағаштың ыдырауы. Әрбір графикалық жиек кейбір ағаш түйіндерінде бірге тізімделген екі төбені біріктіреді, ал әрбір графикалық шыңдар ағаштың сабақтас тармақшаларының түйіндерінде тізімделеді. Әр ағаш түйінінде ең көп дегенде үш төбенің тізімдері келтірілген, сондықтан бұл ыдыраудың ені екіге тең.

A ағаштың ыдырауы график G = (V, E) ағаш, Т, түйіндермен X₁, ..., X_n, әрқайсысы қайда X_мен ішкі бөлігі болып табылады V, келесі қасиеттерді қанағаттандыру^[2] (термин түйін шыңына сілтеме жасау үшін қолданылады Т шыңдарымен шатастырмау үшін G):

Барлық жиынтықтардың бірігуі X_мен тең V. Яғни, әрбір графикалық шыңдар кем дегенде бір ағаш түйінінде болады.
Егер X_мен және X_j екеуінде де шың бар v, содан кейін барлық түйіндер X_к туралы Т арасындағы (ерекше) жолда X_мен және X_j қамтуы керек v сонымен қатар. Тиісті түрде, шыңы бар ағаш түйіндері v байланысты кіші ағашты құрайды Т.
Әр шеті үшін (v, w) графикте ішкі жиын бар X_мен екеуін де қамтиды v және w. Яғни, шыңдар графикте тек сәйкес ішкі ағаштардың түйіні ортақ болған кезде көршілес болады.

The ені ағаштың ыдырауы - бұл оның ең үлкен жиынтығының мөлшері X_мен минус біреу. The кеңдік екі (G) графиктің G - бұл барлық мүмкін ағаштардың ыдырауы арасындағы ең төменгі ен G. Бұл анықтамада ағаштың енін біреуіне тең ету үшін ең үлкен жиынтықтың біреуі кішірейеді.

Эквивалентті, оның кеңдігі G ең үлкенінің бірінен кіші клика ішінде аккордтық график құрамында G ең кішісімен клик нөмірі. Осы клик өлшемімен аккордтық графикті қосу арқылы алуға болады G екеуі де жиындардың кем дегенде біреуіне жататын әрбір екі төбенің арасындағы жиек X_мен.

Төмен ені сонымен қатар сипатталуы мүмкін паналар, белгілі бір уақытқа жалтару стратегиясын сипаттайтын функциялар іздеу-жалтару графикте анықталған ойын. График G кеңдігі бар к егер ол тек тәртіптің панасы болса ғана к + 1 бірақ жоғары тәртіп жоқ, мұнда тәртіп панасы бар к + 1 функция болып табылады β бұл әр жиынтығын бейнелейді X ең көп дегенде к шыңдар G байланыстырылған компоненттерінің біріне G \ X және бұл сәйкес келеді монотондылық меншік β(Y) ⊆ β(X) қашан болса да X ⊆ Y.

A қыңыр 3 × 3 торлы графиктегі төртінші рет, олардың болуы графиктің кемінде 3 ені бар екенін көрсетеді

Ұқсас сипаттаманы қолдану арқылы да жасауға болады шағылдар, бір-біріне тиетін байланыстырылған субографтардың жанұялары (олар шыңмен бөлісетінін немесе шетінен байланысқанын білдіретін).^[3] Брамблдың тәртібі - ең кішкентай соққы жиынтығы ішкі графика отбасы үшін, ал графиктің ені сызықтықтың максималды ретінен бір кем.

Мысалдар

Әрқайсысы толық граф Қ_n кеңдігі бар n - 1. Мұны аккордтық графиктер бойынша кеңдік анықтамасын қолдану арқылы оңай байқауға болады: толық график қазірдің өзінде аккордты, ал одан да көп жиектер қосу оның ең үлкен кликасының өлшемін азайта алмайды.

Кем дегенде екі төбесі бар қосылған графиктің ені 1, егер ол ағаш болса ғана. Ағаштың толық ені бірдей графикамен бірдей дәлдікке ие (атап айтқанда, ол хордалды және максималды өлшемі екі). Керісінше, егер графиктің циклі болса, онда әрбір аккордты аяқтау графикке циклдің қатарынан үш шыңдарынан тұратын кем дегенде бір үшбұрыш кіреді, одан оның ені кемінде екі болады.

Кеңдік кеңдігі

Кеңейтілген ені бар графикалық отбасылар

Кез келген тұрақты шама үшін к, ең үлкен графиктер к деп аталады жартылай к- ағаштар. Шектелген ені бар басқа графикалық отбасыларға мыналар жатады кактус графиктері, жалған ормандар, қатарлы параллель графиктер, сыртқы жоспарлы графиктер, Галин графиктері, және Аполлондық желілер.^[4] The ағындық графиктерді басқару туындаған жинақтау туралы құрылымдық бағдарламалар сияқты белгілі бір міндеттерді орындауға мүмкіндік беретін шектеулі кеңдікке ие тіркеу бөлу оларға тиімді орындалуы керек.^[5]

The жазықтық графиктер шектелген кеңдік жоқ, өйткені n × n тор сызбасы - дәл ені бар жазықтық график n. Сондықтан, егер F Бұл шағын-жабық графтар отбасы шектелген кеңдікпен, оған барлық жазықтық графиктер кіре алмайды. Керісінше, егер кейбір жоспарлы графтар отбасындағы графиктер үшін минор ретінде орын алмаса F, онда тұрақты болады к барлық графиктер F ені ең көбі к. Яғни келесі үш шарт бір-біріне баламалы:^[6]

F шекаралас графиктің кішігірім тұйықталған отбасы;
Тыйым салынған көптеген кәмелетке толмағандардың бірі F жазық;
F барлық жоспарлы графиктерді қамтымайтын кішігірім тұйықталған графтар отбасы.

Кәмелетке толмағандарға тыйым салынады

Үш жолға тыйым салынған кәмелетке толмаған төрт бала: Қ₅ (жоғарғы сол жақта), октаэдр графигі (төменгі сол жақта), Вагнер графигі (жоғарғы оң жақта) және бесбұрышты призманың графигі (төменгі оң жақта)

Әрбір шекті мәні үшін к, ең үлкен графиктер к шектеулі жиынтығымен сипатталуы мүмкін тыйым салынған кәмелетке толмағандар. (Яғни кез-келген кеңдік графигі>к жиынға графтардың бірін кәмелетке толмаған ретінде енгізеді.) тыйым салынған кәмелетке толмағандардың осы жиынтығының әрқайсысы кем дегенде бір жазықтық графиканы қамтиды.

Үшін к = 1, бірегей тыйым салынған минор - 3 шың цикл графигі.^[7]
Үшін к = 2, бірегей тыйым салынған минор - 4 шың толық граф Қ₄.^[7]
Үшін к = 3, тыйым салынған кәмелетке толмаған төрт бала бар: Қ₅, графигі октаэдр, бесбұрышты призмалық график, және Вагнер графигі. Оның ішінде екеуі көпжақты графиктер жазық.^[8]

Үлкен мәндері үшін к, тыйым салынған кәмелетке толмағандардың саны, кем дегенде, квадрат түбірдің экспоненциалына тез өседік.^[9] Алайда, тыйым салынған кәмелетке толмағандардың мөлшері мен санының белгілі жоғарғы шекаралары осы төменгі шекарадан әлдеқайда жоғары.^[10]

Алгоритмдер

Кеңдікті есептеу

Берілген графиктің бар-жоғын анықтау үшін NP аяқталды G ең көбі берілген айнымалыға ие к.^[11]Алайда, қашан к - кез-келген тұрақты шама, ені графиктер к және ені танылуы мүмкін к олар үшін сызықтық уақытта салынған ағаштың ыдырауы.^[12] Бұл алгоритмнің уақытқа тәуелділігі к экспоненциалды болып табылады.

Кеңдіктің өрісі өте көп рөлде болғандықтан, графиктің енін есептейтін әр түрлі практикалық және теориялық алгоритмдер жасалды. Қолда бар бағдарламаға байланысты жақындаудың жақсырақ коэффициентін немесе кіріс немесе кеңдік өлшемінен жұмыс уақытындағы тәуелділікті жақсырақ таңдауға болады. Төмендегі кестеде кейбір кеңдік алгоритмдеріне шолу берілген. Мұнда ${ displaystyle k}$ бұл кеңдік және ${ displaystyle n}$ - бұл кіріс графиктің төбелерінің саны ${ displaystyle G}$ .Алгоритмдердің әрқайсысы уақытында шығады ${ displaystyle f (k) cdot g (n)}$ жуықтау бағанында берілген еннің ыдырауы. Мысалы, алгоритмі Bodlaender (1996) уақытында ${ displaystyle O (k ^ {O (k ^ {3})}) cdot n}$ не кіріс графигінің ағаш ыдырауын салады ${ displaystyle G}$ ені ең көбі ${ displaystyle k}$ немесе оның кеңдігі деп хабарлайды ${ displaystyle G}$ артық ${ displaystyle k}$ . Сол сияқты, алгоритмі Bodlaender және басқалар. (2016) уақытында ${ displaystyle 2 ^ {O (k)} cdot n}$ не кіріс графигінің ағаш ыдырауын салады ${ displaystyle G}$ ені ең көбі ${ displaystyle 5k + 4}$ немесе оның кеңдігі деп хабарлайды ${ displaystyle G}$ артық ${ displaystyle k}$ .

Жақындау	f (k)	g (n)	анықтама
дәл	${ displaystyle O (1)}$	${ displaystyle O (n ^ {k + 2})}$	Арнборг, Корнейл және Проскуровски (1987)
${ displaystyle 4k + 3}$	${ displaystyle O (3 ^ {3k})}$	${ displaystyle O (n ^ {2})}$	Робертсон және Сеймур (1995)
дәл	${ displaystyle k ^ {O (k ^ {3})}}$	${ displaystyle O (n)}$	Bodlaender (1996)
${ displaystyle O (k cdot { sqrt { log k}})}$	${ displaystyle O (1)}$	${ displaystyle n ^ {O (1)}}$	Фейдж, Хаджиагайи және Ли (2008)
дәл	${ displaystyle O (1)}$	${ displaystyle O (1.7347 ^ {n})}$	Fomin, Todinca & Villanger (2015)
${ displaystyle 5k + 4}$	${ displaystyle 2 ^ {O (k)}}$	${ displaystyle O (n)}$	Bodlaender және басқалар. (2016)
${ displaystyle k ^ {2}}$	${ displaystyle O (k ^ {7})}$	${ displaystyle O (n log n)}$	Фомин және басқалар. (2018)

Математикадағы шешілмеген мәселе:

Төменгі мүмкін жазықтық графиктер көпмүшелік уақытта есептелінеді ме?

(математикадағы шешілмеген мәселелер)

Кеңдігінің анықталғаны белгісіз жазықтық графиктер толық NP немесе олардың кеңдігін полиномдық уақытта есептеуге бола ма.^[13]

Іс жүзінде. Алгоритмі Шойхет және Гейгер (1997) графиктердің енін 100 төбеге дейін және кеңдікті 11-ге дейін анықтай алады, бұл графиктердің оңтайлы енімен аккордтық аяқталуын табады.

Ұзындығы аз графиктер бойынша басқа есептер шығару

1970 жылдардың басында графиктерде анықталған комбинаторлық оңтайландыру есептерінің үлкен сыныбын сериялық емес жолмен тиімді шешуге болатындығы байқалды. динамикалық бағдарламалау графтың шегі болғанша өлшем,^[14] теңдеуі көрсетілген параметр Bodlaender (1998). Кейінірек, бірнеше авторлар 1980 жылдардың соңында өздігінен бақылаулар жүргізді^[15] көптеген алгоритмдік есептер NP аяқталды ерікті графиктерді тиімді шешуге болады динамикалық бағдарламалау осы графиктердің ағаш-ыдырауын қолдана отырып, шектелген кеңдік графиктері үшін.

Мысал ретінде бояу кеңдік графигі к а көмегімен шешілуі мүмкін динамикалық бағдарламалау графиктің ағаштың ыдырауы бойынша алгоритм. Әр жиынтық үшін X_мен ағаштың ыдырауы және әрқайсысы бөлім шыңдарының X_мен алгоритм сол түстерде есептелетін және сақталатын ұқсас типтегі мәліметтерді біріктіру арқылы түстердің жарамдылығын және ағаштың ыдырауындағы барлық ұрпақ түйіндеріне таралуын анықтайды. Нәтижесінде алынған алгоритм an-дің оңтайлы бояуын табады nуақыт бойынша шыңдар графигі O(к^к + O(1)n), бұл проблеманы тудыратын уақыт қозғалмайтын параметр.

Курсель теоремасы

Есептердің үлкен сыныбы үшін, егер а-дан есеп шығаратын болса, сызықтық уақыт алгоритмі бар ағаштың ыдырауы тұрақты шектелген кеңдікпен қамтамасыз етілген. Нақтырақ айтқанда, Курсель теоремасы^[16]^[17] егер графикалық есепті графиктердің логикасы қолдану монадалық екінші ретті логика, содан кейін оны сызықтық уақытта шешілген графиктер бойынша ені шектеулі болады. Монадалық екінші ретті логика - бұл келесі құрылымдарды қолданатын графикалық қасиеттерді сипаттайтын тіл: логикалық операциялар ( ${ displaystyle wedge, vee, neg, Rightarrow}$ ), мүшелік тесттер (мысалы, ${ displaystyle e in E, v in V}$ ), шыңдар, шеттер, шыңдар жиектері, жиектер жиынтығы (мысалы, ${ displaystyle forall}$ ${ displaystyle v in V}$ , ${ displaystyle бар}$ ${ displaystyle e in E}$ , ${ displaystyle бар}$ ${ displaystyle I subseteq V}$ , ${ displaystyle forall}$ ${ displaystyle F subseteq E}$ ), көршілестік сынақтары (сен соңғы нүктесі болып табылады e) және оңтайландыру сияқты нәрселерге мүмкіндік беретін кейбір кеңейтімдер.

Мысалға қарастырайық 3-бояу мәселесі графиктер үшін. График үшін ${ displaystyle G = (V, E)}$ , бұл мәселе әр шыңды тағайындауға болатындығын сұрайды ${ displaystyle v in V}$ Екі түстің біріне бірдей түс берілмейтін 3 түстің бірі, бұл мәселені монадалық екінші ретті логикада келесідей түрде көрсетуге болады:

{ displaystyle бар W_ {1} кіші V: бар W_ {2} кіші топ: V бар: W_ {3} кіші субекст V: forall v in V: (v in W_ {1} vee v in W_ {2} vee v in 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 in W_ {2} wedge w in W_ {2}) wedge neg (v in W_ {3} wedge w in W_ {3}))}

,

қайда ${ displaystyle W_ {1}, W_ {2}, W_ {3}}$ 3 түстің әрқайсысына ие шыңдардың ішкі жиынтықтарын бейнелейді, сондықтан Курсельдің нәтижелері бойынша 3 бояу есебін сызықтық уақыт ішінде графикалық сызық бойынша шешуге болады.

Байланысты параметрлер

Түбі

The жол ені Графиктің ағаштың ыдырауының кеңдігіне өте ұқсас анықтамасы бар, бірақ ағаштың ыдырауымен шектеледі, онда негізгі ыдырау ағашы жол графигі. Сонымен қатар, жолдың енін келесіден анықтауға болады аралық графиктер аккордтық графиктен жоғары кеңдікті анықтауға ұқсас. Нәтижесінде графиктің ені әрқашан кем дегенде оның кеңдігімен бірдей үлкен болады, бірақ ол логарифмдік коэффициенттің көмегімен үлкенірек бола алады.^[4] Тағы бір параметр графикалық өткізу қабілеттілігі, бастап аналогтық анықтамасы бар тиісті интервалдық графиктер, және, кем дегенде, жолдың ені сияқты үлкен. Басқа қатысты параметрлерге мыналар жатады ағаштың тереңдігі, егер кішігірім тұйықталған графтар отбасы үшін шектелген сан болса, егер ол тек отбасы жолды қоспағанда және деградация, графиктің сиректілігінің өлшемі, ол ең көбі оның еніне тең.

Тордың кіші өлшемі

Себебі ан n × n тор сызбасы болып табылады n, графиктің ені G әрқашан ең үлкен квадрат тордың өлшемінен үлкен немесе тең кәмелетке толмаған туралы G. Басқа бағытта тор минор теоремасы арқылы Робертсон және Сеймур функциясы бар екенін көрсетеді f көлденеңдігі ең көп дегенде f(р) қайда р минордың ең үлкен квадрат торының өлшемі.^[18] Белгілі ең жақсы шектер f солай ма? f кем дегенде Ω болуы керекр^г.) кейбір тұрақты шама үшін г.> 0, ал ең көп дегенде O (√р/ журнал р).^[19] Шектелген графтар отбасыларымен қатаң шекаралар белгілі, бұл теория бойынша сол отбасыларда графикті оңтайландырудың көптеген мәселелерінің тиімді алгоритмдеріне әкеледі. екі өлшемділік.^[20]Халин торының теоремасы шексіз графиктер үшін кеңдік пен тордың кіші өлшемі арасындағы қатынастың аналогын ұсынады.^[21]

Диаметрі және жергілікті ені

Отбасы F Графиктердің ішкі графикасын алу кезінде жабылған деп айтылады шектелген жергілікті кеңдікнемесе диаметрі-кеңдік қасиеті, егер отбасындағы графиктердің кеңдігі болса жоғарғы шекара олардың функциясы бойынша диаметрі. Егер сынып сонымен қатар қабылдау аяқталған деп есептелсе кәмелетке толмағандар, содан кейін F егер олардың біреуі болса ғана жергілікті кеңдікті шектейді тыйым салынған кәмелетке толмағандар үшін F болып табылады шыңдар сызбасы.^[22] Бұл нәтиженің алғашқы дәлелдері көрсеткендей, шыңы минорсыз графтар жанұясындағы кеңдік диаметрдің функциясы ретінде ең көп дегенде екі есе геометриялық өседі;^[23] кейінірек бұл жеке экспоненциалды деңгейге дейін азайтылды^[20] ақырында сызықтық шекараға дейін.^[24]Шектелген жергілікті кеңдік алгоритмдік теориямен тығыз байланысты екі өлшемділік,^[25] және бірінші ретті логикада анықталатын кез-келген графиктің қасиеті шыңсыз минорсыз графтар отбасы үшін шамалы ғана супер сызықтық болатын уақыт ішінде шешілуі мүмкін.^[26]

Сондай-ақ, кәмелетке толмағандар үшін жабылмаған графиктер сыныбының жергілікті ені шектелген болуы мүмкін. Атап айтқанда, бұл шектелген градустық графиктер класы үшін өте маңызды, өйткені шекаралас диаметрлі ішкі графиктердің өлшемдері бар. Келесі мысал келтірілген 1-жазықтық графиктер, жазықтықта бір шеті бойынша бір қиылысу арқылы жүргізуге болатын графиктер, және тұтастай алғанда бір шеті бойынша шектелген қиылысу саны бар шектелген тектің бетіне түсіруге болатын графиктер үшін. Шектелген жергілікті кеңдіктің кішігірім тұйықталған графикалық жанұяларындағы сияқты, бұл қасиет те осы графиктердің тиімді алгоритмдеріне жол көрсетті.^[27]

Хадвигер нөмірі және S-функциялар

Халин (1976) өзі шақыратын графикалық параметрлер класын анықтайды S-кеңістікті қамтитын функциялар. Бұл функциялар графиктерден бүтін сандарға дейін нөлге тең болуы керек шеттері жоқ графиктер, болу минор-монотонды (функция f егер «минор-монотонды» деп аталады H кәмелетке толмаған G, біреуінде f (H) ≤ f (G)) бар, ол барлық алдыңғы шыңдарға іргелес жаңа шың қосылған кезде бір-біріне ұлғаяды және а-ның екі жағындағы екі ішкі графикадан үлкен мән алынады клика бөлгіш. Осындай функциялардың жиынтығы а толық тор элементтік азайту және максимизациялау операциялары бойынша. Бұл тордағы жоғарғы элемент - кеңдік, ал төменгі элемент - Хадвигер нөмірі, үлкені толық кәмелетке толмаған берілген графикте.

Ескертулер

^ Диестель (2005) 355–355 беттер
^ Диестель (2005) 12.3 бөлім
^ Сеймур және Томас (1993).
^ ^а ^б Bodlaender (1998).
^ Thorup (1998).
^ Робертсон және Сеймур (1986).
^ ^а ^б Bodlaender (1988).
^ Арнборг, Проскуровски және Корнейл (1990); Сатянараяна және Тунг (1990).
^ Рамачандрамурти (1997).
^ Лагергрен (1993).
^ Арнборг, Корнейл және Проскуровски (1987).
^ Bodlaender (1996).
^ Као (2008).
^ Бертеле және Бриоски (1972).
^ Арнборг және Проскуровски (1989); Берн, Лоулер және Вонг (1987); Bodlaender (1988).
^ Курсель, Б. (1990). «I графиктердің монадалық екінші ретті логикасы: ақырлы графиктердің танылатын жиынтықтары». Ақпарат және есептеу. 85: 12–75. CiteSeerX 10.1.1.158.5595. дои:10.1016 / 0890-5401 (90) 90043-сағ.
^ Курсель, Б. (1992). «ІІІ графиктердің монадалық екінші ретті логикасы: кеңдік, тыйым салынған кәмелетке толмағандар және күрделі мәселелер». Informatique Théorique (26): 257–286.
^ Робертсон, Сеймур. Графикалық кәмелетке толмағандар. V. Пландық графиканы қоспағанда. [1]
^ Чекури және Чужой (2016). Төменгі шекарадағы Ω жазбасы үшін қараңыз үлкен O белгісі.
^ ^а ^б Демейн және Хаджиагайи (2008).
^ Диестель (2004).
^ Эппштейн (2000).
^ Эппштейн (2000); Демейн және Гаджиагайи (2004а).
^ Демейн және Хаджиагайи (2004б).
^ Демейн және басқалар. (2004); Демейн және Хаджиагайи (2008).
^ Frick & Grohe (2001).
^ Григорьев және Бодлаендер (2007).

Әдебиеттер тізімі

Арнборг, С .; Корнейл, Д.; Проскуровский, А. (1987), «а к-ағаш », Матрицалық анализ және қосымшалар туралы SIAM журналы, 8 (2): 277–284, дои:10.1137/0608024.
Арнборг, Стефан; Проскуровский, Анджей; Корнейл, Дерек Г. (1990), «Жартылай 3 ағашқа тыйым салынған кәмелетке толмағандардың мінездемесі», Дискретті математика, 80 (1): 1–19, дои:10.1016 / 0012-365X (90) 90292-P, МЫРЗА 1045920.
Арнборг, С .; Proskurowski, A. (1989), «NP қиын есептер үшін сызықтық уақыт алгоритмдері ішінара шектелген к-ағаштар », Дискретті қолданбалы математика, 23 (1): 11–24, дои:10.1016 / 0166-218X (89) 90031-0.
Берн, М. В .; Lawler, E. L.; Вонг, Л.Л. (1987), «Ыдырайтын графиктердің оңтайлы ішкі графикаларын сызықтық уақыт бойынша есептеу», Алгоритмдер журналы, 8 (2): 216–235, дои:10.1016/0196-6774(87)90039-3.
Бертеле, Умберто; Бриошки, Франческо (1972), Нонериалды динамикалық бағдарламалау, Academic Press, 37–38 б., ISBN 978-0-12-093450-8.
Бодлаендер, Ханс Л. (1988), «шекарасы ені бар графиктер бойынша динамикалық бағдарламалау», Proc. Автоматика, тілдер және бағдарламалау бойынша 15-ші халықаралық коллоквиум, Информатикадағы дәрістер, 317, Springer-Verlag, 105–118 бб, CiteSeerX 10.1.1.18.8503, дои:10.1007/3-540-19488-6_110, ISBN 978-3-540-19488-0.
Бодлаендер, Ханс Л. (1996), «Ұзындығы ені бойынша ағаш-ыдырауды табудың сызықтық алгоритмі», Есептеу бойынша SIAM журналы, 25 (6): 1305–1317, CiteSeerX 10.1.1.19.7484, дои:10.1137 / S0097539793251219.
Бодлаендер, Ханс Л. (1998), «Ішінара к- шекарасы ені бар графиктердің дендросы », Теориялық информатика, 209 (1–2): 1–45, дои:10.1016 / S0304-3975 (97) 00228-4.
Бодлаендер, Ганс Л .; Дранж, Пал Дж.; Дреги, Маркус С .; Фомин, Федор V .; Локштанов, Даниэль; Пилипчук, Михал (2016), «A c ^ k n 5-жылдамдықтың жуықтау алгоритмі», Есептеу бойынша SIAM журналы, 45 (2): 317–378, arXiv:1304.6321, дои:10.1137/130947374.
Чекури, Чандра; Чужой, Джулия (2016), «Тор-минор теоремасының көпмүшелік шектері», ACM журналы, 63 (5): A40: 1–65, arXiv:1305.6577, дои:10.1145/2820609, МЫРЗА 3593966, S2CID 209860422.
Демейн, Эрик Д.; Фомин, Федор V .; Хаджиагайи, МохаммадТаги; Тиликос, Димитриос М. (2004), «Екі өлшемді параметрлер және жергілікті кеңдік», Дискретті математика бойынша SIAM журналы, 18 (3): 501–511, CiteSeerX 10.1.1.107.6195, дои:10.1137 / S0895480103433410, МЫРЗА 2134412.
Демейн, Эрик Д.; Хаджиагайи, Мохаммад Таги (2004а), «кішігірім тұйықталған графикалық отбасылардағы диаметр және кеңдік, қайта қаралды», Алгоритмика, 40 (3): 211–215, дои:10.1007 / s00453-004-1106-1, МЫРЗА 2080518, S2CID 390856.
Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги (2004б), «Жергілікті кеңдік пен сызықтық жергілікті еннің эквиваленттігі және оның алгоритмдік қосымшалары», Дискретті алгоритмдер бойынша он бес жылдық ACM-SIAM симпозиумының материалдары, Нью-Йорк: ACM, 840–849 бет, МЫРЗА 2290974.
Демейн, Эрик Д.; Хаджиагайы, Мохаммад Таги (2008), «Кәмелетке толмағандардың тордың кеңдігі бойынша қос өлшемділіктің қосымшаларымен сызықтығы» (PDF), Комбинаторика, 28 (1): 19–36, дои:10.1007 / s00493-008-2140-4, S2CID 16520181.
Диестел, Рейнхард (2004), «Халин торының теоремасының қысқаша дәлелі», Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 74: 237–242, дои:10.1007 / BF02941538, МЫРЗА 2112834, S2CID 124603912.
Диестель, Рейнхард (2005), Графикалық теория (3-ші басылым), Спрингер, ISBN 978-3-540-26182-7.
Эппштейн, Д. (2000), «Кішкентай тұйықталған графикалық отбасылардағы диаметрі мен кеңдігі», Алгоритмика, 27 (3–4): 275–291, arXiv:математика / 9907126, дои:10.1007 / s004530010020, МЫРЗА 1759751, S2CID 3172160.
Фейдж, Уриэль; Хаджиагайи, МохаммадТаги; Ли, Джеймс Р. (2008), «Төменгі салмақты шыңдарды бөлгіштерге арналған жақсару алгоритмдері», Есептеу бойынша SIAM журналы, 38 (2): 629–657, CiteSeerX 10.1.1.597.5634, дои:10.1137 / 05064299X.
Фрик, Маркус; Гроэ, Мартин (2001), «Жергілікті ағаштармен ыдырайтын құрылымдардың бірінші реттік қасиеттерін шешу», ACM журналы, 48 (6): 1184–1206, arXiv:cs / 0004007, дои:10.1145/504794.504798, МЫРЗА 2143836, S2CID 999472.
Фомин, Федор V .; Локштанов, Даниэль; Саурабх, Сакет; Пилипчук, Михал; Врочна, Марцин (2018), «Төмен жылдамдықты графиктер мен матрицалар үшін толық полиномдық уақыттық параметрлермен есептеулер», ACM транс. Алгоритмдер, 14 (3): 34:1–34:45, arXiv:1511.01379, дои:10.1145/3186898, S2CID 2144798.
Григорьев, Александр; Бодлаендер, Ханс Л. (2007), «Бір шеті аз қиылысатын енгізілетін графиктердің алгоритмдері», Алгоритмика, 49 (1): 1–11, CiteSeerX 10.1.1.65.5071, дои:10.1007 / s00453-007-0010-x, МЫРЗА 2344391, S2CID 8174422.
Халин, Рудольф (1976), "S- графикаға арналған функциялар », Геометрия журналы, 8 (1–2): 171–186, дои:10.1007 / BF01917434, S2CID 120256194.
Као, Мин-Ян, ред. (2008), «Графиктердің кеңдігі», Алгоритмдер энциклопедиясы, Springer, б. 969, ISBN 9780387307701, Ұзақ уақыттан бері келе жатқан тағы бір проблема - жоспарлы графиктердің енін есептеудің полиномдық уақыт алгоритмі бар ма.
Лагергрен, Дженс (1993), «Кедергі мөлшерінің жоғарғы шегі», Графикалық құрылым теориясы (Сиэтл, WA, 1991), Қазіргі заманғы математика, 147, Providence, RI: Американдық Математикалық Қоғам, 601-621 б., дои:10.1090 / conm / 147/01202, ISBN 9780821851609, МЫРЗА 1224734.
Рамачандрамурти, Сиддхартан (1997), «Кеңейтуге кедергі құрылымы және саны», Дискретті математика бойынша SIAM журналы, 10 (1): 146–157, дои:10.1137 / S0895480195280010, МЫРЗА 1430552.
Робертсон, Нил; Сеймур, Пол Д. (1984), «Графикалық кәмелетке толмағандар III: жазықтықтағы ағаштың ені», Комбинаторлық теория журналы, В сериясы, 36 (1): 49–64, дои:10.1016/0095-8956(84)90013-3.
Робертсон, Нил; Сеймур, Пол Д. (1986), «Графикалық кәмелетке толмағандар: Пландық графиканы қоспағанда», Комбинаторлық теория журналы, В сериясы, 41 (1): 92–114, дои:10.1016/0095-8956(86)90030-4.
Робертсон, Нил; Сеймур, Пол Д. (1995), «XIII График: Бөлінген жолдар мәселесі», Комбинаторлық теория журналы, В сериясы, 63 (1): 65–110, дои:10.1006 / jctb.1995.1006.
Робертсон, Нил; Сеймур, Пол; Томас, Робин (1994), «Пландық графикті тез алып тастау», Комбинаторлық теория журналы, B сериясы, 62 (2): 323–348, дои:10.1006 / jctb.1994.1073, МЫРЗА 1305057.
Сатянараяна, А .; Тунг, Л. (1990), «Жартылай 3 ағаштың сипаттамасы», Желілер, 20 (3): 299–322, дои:10.1002 / таза 3230200304, МЫРЗА 1050503.
Сеймур, Пол Д.; Томас, Робин (1993), «Графикалық іздеу және ағаш ені үшін минимум-теорема», Комбинаторлық теория журналы, В сериясы, 58 (1): 22–33, дои:10.1006 / jctb.1993.1027.
Шойхет, Кирилл; Гейгер, Дэн (1997), «Оңтайлы триангуляцияларды табудың практикалық алгоритмі», Proc. AAAI '97 (PDF), 185-190 бб.
Торуп, Миккел (1998), «Барлық құрылымдалған бағдарламаларда ағаштың ені аз және регистрдің жақсы бөлінуі бар», Ақпарат және есептеу, 142 (2): 159–181, дои:10.1006 / inco.1997.2697.
Фомин, Федор В.; Тодинка, Иоан; Виллангер, Йнгве (2015), «Триангуляциялар және CMSO арқылы үлкен индукцияланған субографиялар», Есептеу бойынша SIAM журналы, 44 (1): 54–87, arXiv:1309.1559, дои:10.1137/140964801, S2CID 15880453.

[1] Диестель (2005) 355–355 беттер

[2] Диестель (2005) 12.3 бөлім

[3] Сеймур және Томас (1993).

[b98-4] а ^б Bodlaender (1998).

[5] Thorup (1998).

[6] Робертсон және Сеймур (1986).

[b88-7] а ^б Bodlaender (1988).

[8] Арнборг, Проскуровски және Корнейл (1990); Сатянараяна және Тунг (1990).

[FOOTNOTERamachandramurthi1997-9] Рамачандрамурти (1997).

[FOOTNOTELagergren1993-10] Лагергрен (1993).

[FOOTNOTEArnborgCorneilProskurowski1987-11] Арнборг, Корнейл және Проскуровски (1987).

[b96-12] Bodlaender (1996).

[FOOTNOTEKao2008-13] Као (2008).

[FOOTNOTEBertelèBrioschi1972-14] Бертеле және Бриоски (1972).

[15] Арнборг және Проскуровски (1989); Берн, Лоулер және Вонг (1987); Bodlaender (1988).

[16] Курсель, Б. (1990). «I графиктердің монадалық екінші ретті логикасы: ақырлы графиктердің танылатын жиынтықтары». Ақпарат және есептеу. 85: 12–75. CiteSeerX 10.1.1.158.5595. дои:10.1016 / 0890-5401 (90) 90043-сағ.

[17] Курсель, Б. (1992). «ІІІ графиктердің монадалық екінші ретті логикасы: кеңдік, тыйым салынған кәмелетке толмағандар және күрделі мәселелер». Informatique Théorique (26): 257–286.

[18] Робертсон, Сеймур. Графикалық кәмелетке толмағандар. V. Пландық графиканы қоспағанда. [1]

[19] Чекури және Чужой (2016). Төменгі шекарадағы Ω жазбасы үшін қараңыз үлкен O белгісі.

[FOOTNOTEDemaineHajiaghayi2008-20] а ^б Демейн және Хаджиагайи (2008).

[FOOTNOTEDiestel2004-21] Диестель (2004).

[FOOTNOTEEppstein2000-22] Эппштейн (2000).

[23] Эппштейн (2000); Демейн және Гаджиагайи (2004а).

[FOOTNOTEDemaineHajiaghayi2004b-24] Демейн және Хаджиагайи (2004б).

[25] Демейн және басқалар. (2004); Демейн және Хаджиагайи (2008).

[FOOTNOTEFrickGrohe2001-26] Frick & Grohe (2001).

[FOOTNOTEGrigorievBodlaender2007-27] Григорьев және Бодлаендер (2007).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]