Hlavní stránka > Výsledky hledání: Esperet, Louis
Hledej:
Tipy pro vyhledávaní :: Rozšířené hledání
Hledej ve sbírkách:
Seřadit podle: Zobrazit výsledky: Výstupní formát:
Národní úložiště šedé literatury Nalezeno 1 záznamů.  Hledání trvalo 0.00 vteřin. 
Structural aspects of graph coloring
 Pekárek, Jakub ; Dvořák, Zdeněk (vedoucí práce) ; Esperet, Louis (oponent) ; Zhu, Xuding (oponent)
V této práci studujeme strukturální aspekty a algoritmické vlastnosti grafů vnořených nebo reprezentovaných v plochách a s omezeními na jejich stěny nebo cykly. Nejprve navrhneme způsob kvantifikace vlastností toků vnořených v ploše a jeho ap- likací získáváme algoritmus rozhodující rozšířitelnost předbarvení grafů skoro-kvadrangulujících válec, s předbarvenou hranicí válce. Následně vyvineme metodu redukce problému 3- obarvitelnosti grafů vnořených v toru bez trojúhelníků na problém 3-obarvitelnosti skoro- kvadrangulací toru. Získáme praktický algoritmus pro rozhodování 3-obarvitelosti v lineárním čase a pro nalezení 3-barvení v kvadratickém čase. V druhé části zkoumáme vztahy mezi geometrickými reprezentacemi grafů a parame- trem maximální velikost indukovaného pakování lichých cyklů (zkráceně iocp, induced odd cycle packing number). Ukážeme, že v celé řadě tříd geometricky reprezentovatelných grafů je tento parametr omezený, a že tyto třídy jsou χ-omezené (χ-bounded). Na zák- ladě těchto pozorování navrhneme EPTAS pro řešení problému velikosti největší nezávislé množiny pro grafy s omezeným iocp a lineární velikostí vejvětší nezávislé množiny, a také QPTAS pro stejný problém předpokládající pouze omezenost iocp parametru. 1
Úplný záznam

Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.
Digitální repozitář :: Hledej :: Nový záznam :: Personalizace :: Nápověda
Powered by Invenio v1.1.2
Spravuje admin.invenio@techlib.cz
Tato stránka je dostupná také v následujících jazycích:
Česky  English