|
|
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é...
|
|
|
Extension Properties of Graphs and Structures
Klavík, Pavel ; Nešetřil, Jaroslav (vedoucí práce) ; Širáň, Jozef (oponent) ; Hell, Pavol (oponent)
Rozšiřovací vlastnosti grafů a struktur Pavel Klavík Hlavní motivace pro studium kreslení grafů a geometrických reprezentací je najít způ- soby, jak vizualizovat grafy efektivně, aby jejich struktura byla tak srozumitelná, jak je to jenom možné. V této práci se zaměřujeme na strukturální vlastnosti, které vyplývají z toho, že grafy mají určitý druh geometrických reprezentací. Studujeme dva druhy geo- metrických reprezentací: Průnikové reprezentace, ve kterých jsou vrcholy reprezentovány geometrickými množinami, zatímco hrany jsou kódovány jejich průniky, a rovinná vnoření rovinných grafů, což jsou kreslení grafů do roviny bez křížení hran. Z existence geomet- rické reprezentace lze vyvodit dodatečné informace o grafu. Hlavní myšlenka této práce je se ptát, jaká další informace se dá vyvodit ze struktury všech možných geometrických reprezentací. V části I studujeme problém rozšiřování částečných reprezentací pro průnikové reprezen- tace. Vedle grafu obsahuje vstup také částečnou reprezentaci, která předepisuje reprezentaci indukovaného podgrafu. Ptáme se, zdali je možné tuto částečnou reprezentaci rozšířit na plnou reprezentaci vstupního grafu, aniž bychom pozměnili předepsané množiny. Tento pro- blém jsem uvedl v roce 2010 ve své bakalářské práci. Popisujeme přehled známých výsledků pro řadu grafových tříd....
|
|
|
KAM-DIMATIA Series 2004-685 and ITI Series 2004-206. Two algorithms for general list matrix partitions
Sgall, Jiří ; Feder, T. ; Hell, P. ; Králď, D.
List matrix partitions are restricted binary list constraint satisfaction problems which generalize list homomorphisms and many graph partition problems arising, e.g., in the study of perfect graphs. Most of the existing algorithms apply to concrete small matrices, i.e., to partitions problems, provide algorithms for their solution, and discuss their implications.
|
host ::
RSS.