RNDr. Ondřej Suchý, Ph.D.

RNDr. Ondřej Suchý, Ph.D.

RNDr. Dušan Knop, Ph.D.

Katedra teoretické informatiky

Problém nejkratší cesty s minimální excentricitou spočívá v nalezení takové nejkratší cesty v daném grafu, jejíž excentricita je minimální. O problému je známo, že je NP-úplný a W[2]-těžký vzhledem k minimální excentricitě. V práci představujeme FPT algoritmy pro tento problém parametrizované velikostí "maximum leaf number", "neighborhood diversity", "twin cover", "distance to cluster" a kombinací "distance to disjoint paths" s minimální excentricitou. Dále představujeme experimentální vyhodnocení posledního z algoritmů, který jsme také naimplementovali.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

Tato bakalářská práce se zabývá asymetrickým problémem listonoše - speciálním případem optimalizační úlohy z teorie grafů - čínského problému listonoše. Listonošův úkol je stejný jako v tradičním zadání - projít všechny ulice (hrany grafu) a vrátit se do výchozího místa (vrcholu). Oproti tradičnímu zadání tato úloha ale uvažuje graf, jehož neorientované hrany mohou být v každém směru ohodnoceny rozdílně (odtud pochází i anglický název - v ulicích fouká a po větru se jde snáz než opačným směrem proti větru). Cílem práce je vytvoření algoritmu řešícího tento NP-těžký problém. V teoretické části autor vysvětlí zadání problému a jeho variant, popíše možnosti jejich využití v praxi a možné způsoby jejich řešení. V praktické části pak v jazyce C++ implementuje algoritmus řešící tento problém pro případ, kdy jsou v grafu pouze jednotky neorientovaných hran.

RNDr. Ondřej Suchý, Ph.D.

Ing. František Štampach, Ph.D.

Katedra softwarového inženýrství

RNDr. Ondřej Suchý, Ph.D.

Ing. Jiří Novák, Ph.D.

Katedra softwarového inženýrství

Náplňou tejto bakalárskej práce je rozšírenie externej knižnice Boost Graph Library, pracujúcej s grafovou reprezentáciou dát pre programovací jazyk C++. Je pridaná funkcionalita rozpoznávania intervalových grafov a s tým súvisiacich funkcií. Čitateľ je oboznámený s knižnicami Boost Graph Library, Interval Container Library a algoritmami Zjemenie partície, Lex-BFS, Test chordálnosti grafu, Strom klík, Rozpoznávanie intervalového grafu a Konštrukcia intervalového grafu. Následne je rozoberaná implementácia daných algoritmov a použitých štruktúr, s dôrazom na genericitu rozhraní funkcií poskytnutých používateľovi. Časť práce sa venuje testovaniu vypracovaného riešenia. Na záver sú diskutované dosiahnuté časové zložitosti a možné vylepšenia implementácie. Výstupom práce je použiteľné rozšírenie funkcionality Boost Graph Library, dodržiavajúce jej princípy.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

Ing. Michal Valenta, Ph.D.

Katedra softwarového inženýrství

Cílem této bakalářské práce je rozšířit C++ knihovnu Boost Graph Library (BGL) o algoritmy pro získávání stromové dekompozice grafu a příklad algoritmu, který využívá tuto stromovou dekompozici. V práci se čtenář seznámí nejen s jednotlivými algoritmy, ale i se samotnou knihovnou, která bude rozšiřována. Dále se práce zabývá samotnou úspěšnou implementací algoritmů, kde je kladen důraz především na dodržení konvencí knihovny BGL a pravidel generického programování. Závěrem práce hodnotí kvalitu implementace a navrhuje možná zlepšení. Výsledkem práce je funkční rozšíření BGL.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

Ing. František Štampach, Ph.D.

Katedra softwarového inženýrství

RNDr. Ondřej Suchý, Ph.D.

doc. RNDr. Dušan Knop, Ph.D.

Katedra teoretické informatiky

Tato práce se zabývá problémem monitorování hran pomocí vzdáleností. Problém je nejdříve popsán a poté je k němu přistoupeno z pohledu strukturálních parametrů. Algoritmus parametrizovaný velikostí vrcholového pokrytí byl navržen a jeho korektnost byla dokázána. Následně byl implementován a jeho rychlost byla otestována. Algoritmus, jehož parametrem je velikost feedback edge set byl navržen, a následně implementovaný a otestovaný.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

RNDr. Dušan Knop, Ph.D.

Katedra teoretické informatiky

Tato práce se zabývá problémem maximálního hranového q-barvení. Podstatou problému je obarvení hran grafu za použití co nejvyššího počtu barev tak, aby byly hrany vedoucí z jednoho vrcholu obarveny maximálně q různými barvami. Nejdříve zkoumáme již známe algoritmy zabívající se tímto problémem a některé z nich detailně popíšeme. Poté představíme nově vymyšlené algoritmy - jednoduchý algoritmus pro stromy s lineární složitostí a algoritmus pro intervalové grafy s časovou složitostí O(n*(q+1)^p*k^(pq+1)*(q+p)^p), kde n je počet vrcholů grafu, p je velikost největšího úplného podgrafu a k je počet barev v optimálním obarvení. Součástí práce je také implementace algoritmu pro intervalové grafy.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

Tato bakalářská práce se zabývá vytvořením parametrizovaného algoritmu hledajícího geodetické číslo na grafech s nízkým vrcholovým pokrytím. Geodetické číslo je velikost minimální množiny takové, že na nejkratších cestách mezi jednotlivými dvojicemi vrcholů množiny leží všechny vrcholy grafu. Na začátku jsou rozebrány řešení podobných problémů, například parametrizovaný algoritmus pro hledání metrické dimenze grafu. V práci je ukázáno, že lze využít určitých vlastností bipartitních grafů a grafů s nízkým vrcholových pokrytím pro zjednodušení složitosti algoritmu. Popsaný algoritmus je parametrizovaný velikostí množiny vrcholového pokrytí. Algoritmus je implementován v jazyce C++. Testováním byla potvrzena očekávaná redukce složitosti. Tento algoritmus lze tedy s úspěchem používat na zmíněných specifických grafech.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

RNDr. Ondřej Suchý, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

Problém zvaný d-Path Vertex Cover, d-PVC spočívá v nalezení podmnožiny F vrcholů daného grafu G=(V,E) takové, že G \ F neobsahuje žádnou cestu na d vrcholech. Cesty, které chceme takto podchytit, nemusí být indukované. Je známo, že problém d-PVC je NP-úplný pro každé d >= 2. Dále je známo, že problém 5-PVC parametrizovaný velikostí řešení k je řesitelný v čase O(5^k*n^O(1)). V této práci přicházíme s algoritmem používající iterativní kompresi, který řeší problém 5-PVC v čase O(4^k*n^O(1)).

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

Je-li dán vážený graf a podmnožina jeho vrcholů zvaných terminály, problém Steinerova stromu spočívá v nalezení souvislého podgrafu s nejmenší váhou, který obsahuje všechny terminály. Jedná se o známý NP-těžký problém, který nalézá užití kupříkladu v návrhu integrovaných obvodů, nebo počítačových a dopravných sítích. V této práci rozebereme algoritmus od Dreyfuse a Wagnera, od Ericksona, Monmy a Veinotta, a Nederlofův algoritmus, které řeší verzi tohoto problému parametrizovanou počtem terminálů, a algoritmus využívající dynamické programování a matici řezů pro parametrizaci dle stromové šířky. Pro všechny popsané algoritmy vytvoříme optimalizovanou implementaci a pro porovnání s jinými řešeními ukážeme její výsledky v soutěži PACE 2018.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

RNDr. Tomáš Valla, Ph.D.

Katedra teoretické informatiky

Tato práce popisuje řešení problému izomorfismu podgrafů pomocí techniky barevného kódování. V práci je popsán problém izomorfismu podgrafů, jeho varianty a jeho aplikace. Dále je rozebrán problém tvorby hezkého stromového rozkladu optimální šířky pro zadaný graf, jelikož takováto struktura je pro daný přístup vyžadována. Jako hlavní část práce je popsáno několik modifikací a optimalizací původního algoritmu založeného na barevném kódování. Praktickým výsledkem práce je modul implementovaný v jazyce C, který je navržen pro řešení velkých instancí problému izomorfismu podgrafů včetně výpisu nalezených výsledků.

Práce na DSpace

RNDr. Ondřej Suchý, Ph.D.

Mgr. Michal Opler, Ph.D.

Katedra teoretické informatiky

Zabýváme se problémem Rozdělení na indukované hvězdy na neorientovaných grafech. Cílem je rozdělit graf na q množin S_1, ..., S_q tak, že každá množina S_i indukuje hvězdu (graf izomorfní grafu K_{1, r} pro nějaké r >= 0). Je známo, že pro každé pevné q >= 3 je tento problém NP-úplný. Existuje ale exaktní algoritmus, který dokáže rozdělit graf na q indukovaných hvězd v čase 3^n n^{O(1)} a použije polynomiálně mnoho paměti. Není nám známo, že by existoval exaktní parametrizovaný algoritmus pro tento problém. V této práci předvedeme následující výsledky: (1) Problém patří do třídy FPT pokud budeme parametrizovat vrcholovým pokrytím grafu a existuje exaktní algoritmus běžící v čase O(k^{2k+1} n^2), kde k je velikost minimálního vrcholového pokrytí grafu. (2) Problém patří do třídy FPT pokud budeme parametrizovat stromovou šířkou grafu a a existuje exaktní algoritmus běžící v čase O(tw(G)^{2tw(G)}* n), kde tw(G) je stromová šířka grafu. (3) Pro každé pevné q platí, že problém lze vyřešit v lineárním čase na grafech s omezenou klikovou šířkou. Také poskytujeme jednoduchou implementaci algoritmu parametrizovaného vrcholovým pokrytím grafu v jazyce C++ a vyhodnotili jsme výkonnost implementace.

Práce na DSpace