Optimisation using graph searching on special graph classes
| Název práce v češtině: | Řešení optimalizačních problémů prohledáváním na vybraných třídách grafů |
|---|---|
| Název v anglickém jazyce: | Optimisation using graph searching on special graph classes |
| Klíčová slova: | teorie grafů, optimalizace, aproximace, prohledávání grafů, grafové třídy |
| Klíčová slova anglicky: | graph theory, optimisation, approximation, graph searching, graph classes |
| Akademický rok vypsání: | 2013/2014 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | Mgr. Tomáš Gavenčiak, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 05.11.2013 |
| Datum zadání: | 06.11.2013 |
| Datum potvrzení stud. oddělením: | 21.11.2013 |
| Datum a čas obhajoby: | 15.06.2015 00:00 |
| Datum odevzdání elektronické podoby: | 22.05.2015 |
| Datum odevzdání tištěné podoby: | 22.05.2015 |
| Datum proběhlé obhajoby: | 15.06.2015 |
| Oponenti: | doc. Mgr. Robert Šámal, Ph.D. |
| Zásady pro vypracování |
| Cílem práce je prozkoumat vlastnosti a možnosti optimalizačních algoritmů založených na prohledávání grafů (BFD, DFS, LexBFS, ...) na vybraných třídách grafů, a to jak teoreticky, tak praktickými experimenty. U problémů, jejichž řešení tohoto typu je již známo, pak prozkoumat robustnost těchto algoritmů na grafech mimo cílové třídy.
Součástí práce je jak hrubý přehled v posledních výsledcích v této oblasti, tak podrobnější rozpracování jednoho či více problémů a grafových tříd, a to jak teoreticky, tak praktickými experimenty vlastními programy. Práce bude sepsána v angličtině. Český název práce: Optimalizace grafovým prohledáváním na speciálních třídách grafů |
| Seznam odborné literatury |
| Derek G. Corneil, Richard Krueger: A Unified View of Graph Searching. SIAM J. Discrete Math. 22(4): 1259-1276 (2008)
George B. Mertzios, Derek G. Corneil: A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs. SIAM J. Discrete Math. 26(3): 940-963 (2012) Anna Bretscher, Derek G. Corneil, Michel Habib, Christophe Paul: A Simple Linear Time LexBFS Cograph Recognition Algorithm. SIAM J. Discrete Math. 22(4): 1277-1296 (2008) Derek G. Corneil, Stephan Olariu, Lorna Stewart: The LBFS Structure and Recognition of Interval Graphs. SIAM J. Discrete Math. 23(4): 1905-1953 (2009) |
| Předběžná náplň práce |
| Některé optimalizační problémy lze na některých třídách grafů nově efektivně řešit pomocí různých variant grafového prohledávání. Tyto přístupy nejen nabízí nový vhled do známých algoritmů, ale i algoritmy, které i na grafech mimo cílové třídy fungují skoro optimálně. Cílem je prozkoumat tyto případy jak teoreticky, tak praktickými experimenty. |
| Předběžná náplň práce v anglickém jazyce |
| Some optimisation problems on various special graph classes have been recently shown to be efficiently solvable using variants of graph searching algorithms. This approach not only gives new insight into the problem but also yields algorithms working almost optimally outside the intended graph classes. The goal of this project is to examine these cases both theoretically and experimentally. |