|
|
Variants of graph labeling problems
Masařík, Tomáš ; Fiala, Jiří (vedoucí práce) ; Fellows, Michael R. (oponent) ; Hell, Pavol (oponent)
Tato práce se skládá ze tří částí zasvědcených značkování grafů, dědičným grafovým třídám a parametrizované složitosti. Pakovací barvení, původně označované vysílací barevnost, přiřazuje vrcholům grafu přirozená čísla tak, že vrcholy se stejným číslem musí být od sebe vzdáleny alespoň o hodnotu danného čísla. Tento problém je motivován přiřazováním frekvencí vysílačům. My zlepšujeme těžkost na chordálních grafech. Dokazujeme, že pakovací barvení na chordálních grafech diametru 3 je velice těžké aproximovat. Navíc uvádíme několik pozitivních výsledků pro intervalové grafy a pro související strukturální grafové parametry. Dědičné grafové třídy jsou zachovány při mazání vrcholů. My studujeme grafy takové, které neobsahují podgraf H jako svůj indukovaný podgraf. Dokazujeme, že 3 barvení je polynomiálně řešitelné pro (P3 + P4)-free a (P2 + P5)-free grafy, a tudíž jsme vyřešili poslední otevřené případy pro H-free grafy, kde H má nanejvýš 7 vrcholů. Férové problémy jsou takové modifikace grafových mazacích problémů, kde místo minimalizace velikosti řešení, je cílem minimalizovat maximální počet sousedů ve smazané množině. My ukazujeme, že takové problémy jdou vyřešit ve FPT čase pro MSO1 formuli parametrizováno velikostí formule a twin pokrytím grafu. Navíc definujeme základní férový problém, férové...
|
|
|
Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Fellows, Michael R. (oponent) ; Tantau, Till (oponent)
Tato práce podává důkaz existence kompaktních rozšířených formulací pro širokou škálu polytopů souvisejících s problémem omezujících podmínek (CSP), grafovou monadickou logikou druhého řádu (MSO) a rozšířeními MSO, mají-li dané instance omezenou stromovou šířku. Ukážeme, že naše rozšířené formulace mají další užitečné vlastnosti a odkrýváme souvislosti mezi MSO a CSP. Docházíme tak k závěru, že kombinace MSO logiky, CSP a geometrie poskytuje rozšiřitelný rámec pro konstrukci kompaktních rozšířených formulací a parametrizovaných algoritmů pro grafy s omezenou stromovou šířkou. S použitím těchto nástrojů pak zcela zodpovíme otázku parametrizované složitosti různých rozšíření MSO na dvou třídách grafů, konkrétně grafech s omezenou stromovou šířkou a s omezenou různorodostí sousedství. Objevili jsme, že (ne)linearita těchto rozšíření určuje parametrizovanou složitost na grafech s omezenou různorodostí sousedství. Na závěr studujeme tzv. posunutou kombinatorickou optimalizaci, která tvoří nelineární optimalizační rámec zobecňující standardní kombinatorickou optimalizaci. V této oblasti poskytneme prvotní zjištění z perspektivy parametrizované složitosti.
|
host ::
RSS.