|
|
Computational Complexity of Graph Planarity Testing
Krčál, Marek ; Bálek, Martin (vedoucí práce) ; Škovroň, Petr (oponent)
V tomto článku ukážeme, že testování planarity je v SL (symetrický nedeterministický LOGSPACE). Hlavní část našeho důkazu je redukce na problém testování rovinnosti grafu s maximálním stupněm tři. Povšiměte si, že obvyklé nahrazování vrchol větších stupňů "malými kružnicemi" může rovinnost pokazit, musíme si počínat šikovněji. Testování rovinnosti grafu s maximálním stupněm tři už bylo vyřešeno ve článku "Symmetric complementation" Johna Reifa. Už dříve Meena Mahajan a Eric Allender ("Complexity of planarity testing") ukázali, že testování rovinnosti je v SL. Jejich důkaz se však sestává z SL implementace velmi složitého paralelního algoritmu od Johna Reifa a Vijayi Ramachandran ("Planarity testing in parallel"). Ten je však nejspíše zbytečně komplikovaný pro účely prostorové složitosti. Tento výsledek spolu s nedávným průlomem Omera Reingolda dokazujícího, že SL = L ("Undirected ST-connectivity in log-space") zcela řeší otázku složitosti testování planarity, protože to je těžké pro L (toto je též dokázáno v "Complexity of planarity testing"). Zkonstruujeme algoritmus používající logaritmický prostor, který převede vstupní graf G na G0 s maximálním stupněm 3 tak, že G je rovinný tehdy a jen tehdy, když G0 je rovinný.
|
|
|
Nejkratší cesty při vyhledávání dopravního spojení
Hronik, Jan ; Kolman, Petr (vedoucí práce) ; Škovroň, Petr (oponent)
Zabýváme se algoritmy pro hledání nejlepšího spojení podle jízdního řádu, přičemž pojmem nejlepší myslíme nejkratší vzhledem ke zvolenému ohodnocení cest (např. nejrychlejší, nejkratší na počet ujetých km, spojení s nejmenším počtem přestupů). Problém nejkratšího spojení v dopravní síti je formalizován a převeden na problém nejkratší cesty v grafu. K tomu je navržena reprezentace dopravní sítě pomocí orientovaného grafu. Dále je popsáno několik standardních algoritmů pro hledání nejkratších cest v grafu a jejich optimalizace pro použití při hledání dopravních spojení. Nakonec je porovnána výkonnost jednotlivých algoritmů při jejich použití na (1) vlakovou sít pro Českou republiku a (2) na náhodně vygenerovaný graf.
|
|
| |
|
|
Nejkratší cesty při vyhledávání dopravního spojení
Hronik, Jan ; Škovroň, Petr (oponent) ; Kolman, Petr (vedoucí práce)
Zabýváme se algoritmy pro hledání nejlepšího spojení podle jízdního řádu, přičemž pojmem nejlepší myslíme nejkratší vzhledem ke zvolenému ohodnocení cest (např. nejrychlejší, nejkratší na počet ujetých km, spojení s nejmenším počtem přestupů). Problém nejkratšího spojení v dopravní síti je formalizován a převeden na problém nejkratší cesty v grafu. K tomu je navržena reprezentace dopravní sítě pomocí orientovaného grafu. Dále je popsáno několik standardních algoritmů pro hledání nejkratších cest v grafu a jejich optimalizace pro použití při hledání dopravních spojení. Nakonec je porovnána výkonnost jednotlivých algoritmů při jejich použití na (1) vlakovou sít pro Českou republiku a (2) na náhodně vygenerovaný graf.
|
|
| |
|
|
Computational Complexity of Graph Planarity Testing
Krčál, Marek ; Škovroň, Petr (oponent) ; Bálek, Martin (vedoucí práce)
V tomto článku ukážeme, že testování planarity je v SL (symetrický nedeterministický LOGSPACE). Hlavní část našeho důkazu je redukce na problém testování rovinnosti grafu s maximálním stupněm tři. Povšiměte si, že obvyklé nahrazování vrchol větších stupňů "malými kružnicemi" může rovinnost pokazit, musíme si počínat šikovněji. Testování rovinnosti grafu s maximálním stupněm tři už bylo vyřešeno ve článku "Symmetric complementation" Johna Reifa. Už dříve Meena Mahajan a Eric Allender ("Complexity of planarity testing") ukázali, že testování rovinnosti je v SL. Jejich důkaz se však sestává z SL implementace velmi složitého paralelního algoritmu od Johna Reifa a Vijayi Ramachandran ("Planarity testing in parallel"). Ten je však nejspíše zbytečně komplikovaný pro účely prostorové složitosti. Tento výsledek spolu s nedávným průlomem Omera Reingolda dokazujícího, že SL = L ("Undirected ST-connectivity in log-space") zcela řeší otázku složitosti testování planarity, protože to je těžké pro L (toto je též dokázáno v "Complexity of planarity testing"). Zkonstruujeme algoritmus používající logaritmický prostor, který převede vstupní graf G na G0 s maximálním stupněm 3 tak, že G je rovinný tehdy a jen tehdy, když G0 je rovinný.
|
|
| |
host ::
RSS.