Algorithmic Meta-theorems for Restricted Classes of Graphs /
Algoritmické meta-věty jsou matematická tvrzení typu „Pro všechny problémy vyjádřitelné v dané logice existuje efektivní algoritmus na dané třídě grafů“. Jsou důležitým nástrojem na dokazování existence rychlých algoritmů pro těžké problémy na omezených třídách grafů. V této práci podáváme přehled z...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2016
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/172462/fi_d/ |
| Shrnutí: | Algoritmické meta-věty jsou matematická tvrzení typu „Pro všechny problémy vyjádřitelné v dané logice existuje efektivní algoritmus na dané třídě grafů“. Jsou důležitým nástrojem na dokazování existence rychlých algoritmů pro těžké problémy na omezených třídách grafů. V této práci podáváme přehled známých algoritmických meta-vět a dokazujeme několik nových meta-vět. Algoritmické meta-věty se dělí na dva typy v závislosti na logice, pro kterou jsou určeny - algoritmické meta-věty pro monadickou logiku druhého řádu (monadic second order logic, MSO) a algoritmické meta-věty pro logiku prvního řádu (first-order logic, FO). V návaznosti na toto rozlišení se tato práce skládá z dvou částí. V první části se zaobírá Courcellovou větou, která tvrdí, že pro každý problém definovatelný v logice MSO existuje lineární algoritmus na grafech s omezeným parametrem „treewidth“ a rozšířením této věty na grafy s omezeným parametrem „clique width“. Největším nedostatkem těchto výsledků je, že ačkoliv impl Algorithmic meta-theorems are statements of the form "Every problem expressible in a certain logic is efficiently solvable on a certain class of graphs". They are an important tool for establishing tractability of many important and generally hard problems on restricted classes of graphs. In this work we give an overview of known algorithmic metatheorems together with the techniques used in their proofs and prove several metatheorems of our own. Algorithmic metatheorems can roughly be divided into two classes - metatheorems for monadic second-order (MSO) logic and metatheorems for first-order (FO) logic. Following this distinction, this thesis is logically divided into two parts. In the first part we present Courcelle's theorem stating that every MSO definable property admits linear-time algorithm for graph classes of bounded treewidth and its extension to graphs of bounded clique-width proved by Courcelle, Makowski and Rotics. The main shortcomming of these theorems comes from the fac |
|---|---|
| Popis jednotky: | Vedoucí práce: Petr Hliněný |
| Fyzický popis: | x, 117 stran |