Algorithmic metatheorems for matroids
| Název práce v češtině: | Algoritmické metavěty pro matroidy |
|---|---|
| Název v anglickém jazyce: | Algorithmic metatheorems for matroids |
| Klíčová slova: | algoritmy, matroidy, šířkové parametry, FOL vlastnosti, MSOL vlastnosti |
| Klíčová slova anglicky: | algorithms, matroids, width parameters, FOL properties, MSOL properties |
| Akademický rok vypsání: | 2012/2013 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | RNDr. Ondřej Pangrác, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 20.11.2012 |
| Datum zadání: | 03.12.2012 |
| Datum potvrzení stud. oddělením: | 06.12.2012 |
| Datum a čas obhajoby: | 26.01.2015 00:00 |
| Datum odevzdání elektronické podoby: | 05.12.2014 |
| Datum odevzdání tištěné podoby: | 05.12.2014 |
| Datum proběhlé obhajoby: | 26.01.2015 |
| Oponenti: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Zásady pro vypracování |
| Student se seznámí s výsledky v oblasti algoritmických metavět, tj. tvrzení, které říkají, že jistou třídu problémů lze efektivně řešit v omezených třídách vstupů. V práci se pokusí o rozšíření současného stavu poznání převážně v oblasti matroidů.
|
| Seznam odborné literatury |
| T. Gavenčiak, D. Král, S. Il-Oum: Deciding first order logic properties of matroids, arXiv:1108.5457.
J. Flum, M. Grohe: Parametrized complexity theory, Springer, 2006. S. Kreutzer: Algorithmic meta-theorems, arxiv:0902.3616. R. Niedermeier: Invitation to fixed-parameter algorithms, Oxford University Press, 2006. J. Oxley: Matroid theory, Oxford University Press, 2006. |
| Předběžná náplň práce |
| Algoritmické metavěty jsou oblast výsledků, které říkají, že jistou třídu problémů lze efektivně řešit v omezených třídách vstupů. V práci se student pokusí o rozšíření současného stavu poznání převážně v oblasti matroidů. |
| Předběžná náplň práce v anglickém jazyce |
| Algorithmic metatheorems are stateing that a class of problems can be solved efficiently for restrected class of inputs. In this work, the student should try to extend some results on the topic with focus on matroids. |