Discrete methods in computer science /
V této disertační práci je předloženo řešení tří otevřených problémů na rozhraní kombinatoriky a teoretické informatiky. Řešení všech tří problémů jsou založena na nových postupech a metodách, u kterých předpokládáme další využití v oblasti kombinatoriky a teoretické informatiky. Konkrétně vyvineme...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2022
|
| Témata: | |
| On-line přístup: | https://is.muni.cz/th/m9k1z/ |
| Shrnutí: | V této disertační práci je předloženo řešení tří otevřených problémů na rozhraní kombinatoriky a teoretické informatiky. Řešení všech tří problémů jsou založena na nových postupech a metodách, u kterých předpokládáme další využití v oblasti kombinatoriky a teoretické informatiky. Konkrétně vyvineme nové metody pro vnořování hypergrafů do hypergrafů s pozitivní uniformní hranovou hustotou a použijeme tyto metody pro vyřešení otevřeného problému o uniformní turánovského hustotě hypergrafů formulovaného C. Reiherem. Druhý problém, jehož řešení předkládáme, je vyřešení otázky F. Garbeho a kol. o charakterizaci kvazináhodných latinských čtverců, které je založeno na analytických metodách pro studium asymptotických vlastností kombinatorických objektů. Třetí problém patří do oblasti parametrizované složitosti. Navrhneme algoritmus pro hledání rozkladů matroidů a použijeme jej pro návrh efektivních parametrizovaných algoritmů pro problém celočíselného programování, jejichž vstupy mají skrytou In this thesis, we resolve three open problems on the interface of combinatorics and theoretical computer science, with emphasis on developing tools with further application to other problems in the area. Specifically, we develop general methods for embedding hypergraphs in host hypergraphs with positive uniform edge density, thereby solving an open problem of Reiher derivative of the classical Turán problem for hypergraphs. The second problem concerns applying recently developed analytic techniques to asymptotic combinatorial problems to derive a characterisation of quasirandom Latin squares, resolving a question of Garbe et al. The final problem belongs to parameterised complexity where we design new matroid decomposition algorithms and apply them to develop a fixed parameter tractable algorithm that uncovers hidden block structure in integer programming instances. |
|---|---|
| Popis jednotky: | Vedoucí práce: Daniel Kráľ |
| Fyzický popis: | vi, 148 stran : ilustrace |