Hlavní stránka > Výsledky hledání: keywords:"průnikové třídy grafů"
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.01 vteřin. 
Algorithmic aspects of intersection-defined graph classes
 Jedličková, Nikola ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
Geometricky reprezentovatel'né triedy grafov sú intenzívne študovanou oblast'ou výskumu v súčasnej literatúre, a to kvôli ich štrukturálnym charakterizáciám a efektívnym algoritmom. Najštudovanejšou triedou takých grafov je trieda intervalových grafov. V tejto práci sa za- meriame na dva problémy, zovšeobecňujúce problém rozpoznávania, pre triedy súvisiace s triedou intervalových grafov. V prvej časti sa zaoberáme tzv. zarovnanými intervalovými digrafmi. Táto trieda bola skúmaná ako správna analógia intervalových grafov. Pre intervalové grafy sú známe algo- ritmy pre rozširovanie čiastočných reprezentácií daných intervalov na úplnú intervalovú re- prezentáciu. My predstavíme podobný problém - rozširovanie čiastočných usporiadaní - a ukážeme polynomiálny algoritmus pre rozširovanie čiastočných usporiadaní zarovnaných intervalových digrafov. V druhej časti práce dokážeme NP-úplnost' pre dva špeciálne prípady problému simultánnych reprezentácií grafov, ktorý predstavil Jampani a Lubiw. Problém simultánnych reprezentácií pre danú triedu grafov sa pýta, či k grafov môže byt' reprezentovaných tak, že každý vrchol je reprezentovaný rovnakým objektom v každej reprezentácii. Dokázali sme, že tento problém je...
Ú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