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...

Celý popis

Uloženo v:
Podrobná bibliografie
Hlavní autor: Gajarský, Jakub (Autor práce)
Další autoři: Hliněný, Petr, 1971- (Vedoucí práce)
Typ dokumentu: VŠ práce nebo rukopis
Jazyk:Angličtina
Vydáno: 2016
Témata:
algoritmy (programování)
grafové algoritmy
teorie grafů
computer algorithms
graph algorithms
graph theory
disertace
dissertations
On-line přístup:http://is.muni.cz/th/172462/fi_d/
Obálka
LEADER 05923ctm a22009377i 4500
001 MUB01006376203
003 CZ BrMU
005 20240516152301.0
008 160922s2016 xr ||||| |||||||||||eng d
STA |a POSLANO DO SKCR  |b 2016-12-16 
035 |a (ISMU-VSKP)225879 
040 |a BOD114  |b cze  |d BOD018  |e rda 
072 7 |a 004.4/.6  |x Programování. Software  |2 Konspekt  |9 23 
072 7 |a 519.1/.8  |x Kombinatorika. Teorie grafů. Matematická statistika. Operační výzkum. Matematické modelování  |2 Konspekt  |9 13 
080 |a 004.421  |2 MRF 
080 |a 519.178  |2 MRF 
080 |a 519.17  |2 MRF 
100 1 |a Gajarský, Jakub  |% UČO 172462  |* [absolvent FI MU]  |4 dis 
242 1 0 |a Algorithmic Meta-theorems for Restricted Classes of Graphs  |y eng 
245 1 0 |a Algorithmic Meta-theorems for Restricted Classes of Graphs /  |c Jakub Gajarský 
264 0 |c 2016 
300 |a x, 117 stran 
336 |a text  |b txt  |2 rdacontent 
337 |a bez média  |b n  |2 rdamedia 
338 |a svazek  |b nc  |2 rdacarrier 
500 |a Vedoucí práce: Petr Hliněný 
502 |a Dizertace (Ph.D.)--Masarykova univerzita, Fakulta informatiky, 2016 
520 2 |a 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  |% cze 
520 2 9 |a 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  |9 eng 
650 0 7 |a algoritmy (programování)  |7 ph131788  |2 czenas 
650 0 7 |a grafové algoritmy  |7 ph770865  |2 czenas 
650 0 7 |a teorie grafů  |7 ph126555  |2 czenas 
650 0 9 |a computer algorithms  |2 eczenas 
650 0 9 |a graph algorithms  |2 eczenas 
650 0 9 |a graph theory  |2 eczenas 
655 7 |a disertace  |7 fd132024  |2 czenas 
655 9 |a dissertations  |2 eczenas 
658 |a Informatika (čtyřleté)  |b Informatika  |c FI D-IN4 IN (IN)  |2 CZ-BrMU 
700 1 |a Hliněný, Petr,  |d 1971-  |7 mub2013777090  |% UČO 168881  |4 ths 
710 2 |a Masarykova univerzita.  |b Katedra teorie programování  |4 dgg 
856 4 1 |u http://is.muni.cz/th/172462/fi_d/ 
CAT |c 20160922  |l MUB01  |h 0421 
CAT |a HANAV  |b 02  |c 20160926  |l MUB01  |h 1051 
CAT |a POSPEL  |b 02  |c 20160927  |l MUB01  |h 0740 
CAT |a POSPEL  |b 02  |c 20160927  |l MUB01  |h 0741 
CAT |a VESELA  |b 02  |c 20161201  |l MUB01  |h 1010 
CAT |c 20161216  |l MUB01  |h 1323 
CAT |a POSPEL  |b 02  |c 20170228  |l MUB01  |h 1036 
CAT |a POSPEL  |b 02  |c 20170302  |l MUB01  |h 0828 
CAT |a POSPEL  |b 02  |c 20180314  |l MUB01  |h 0814 
CAT |a POSPEL  |b 02  |c 20180503  |l MUB01  |h 0729 
CAT |a POSPEL  |b 02  |c 20180710  |l MUB01  |h 0635 
CAT |a POSPEL  |b 02  |c 20190213  |l MUB01  |h 0800 
CAT |a POSPEL  |b 02  |c 20190924  |l MUB01  |h 0745 
CAT |a POSPEL  |b 02  |c 20200510  |l MUB01  |h 2306 
CAT |a POSPEL  |b 02  |c 20201212  |l MUB01  |h 2150 
CAT |a POSPEL  |b 02  |c 20210122  |l MUB01  |h 0054 
CAT |a POSPEL  |b 02  |c 20210322  |l MUB01  |h 1142 
CAT |a POSPEL  |b 02  |c 20210327  |l MUB01  |h 0026 
CAT |c 20210614  |l MUB01  |h 1021 
CAT |c 20210614  |l MUB01  |h 2008 
CAT |a BATCH  |b 00  |c 20210724  |l MUB01  |h 1249 
CAT |a POSPEL  |b 02  |c 20210912  |l MUB01  |h 2336 
CAT |a POSPEL  |b 02  |c 20211010  |l MUB01  |h 2218 
CAT |a REPISOVA  |b 02  |c 20211018  |l MUB01  |h 1713 
CAT |a HANAV  |b 02  |c 20211122  |l MUB01  |h 1504 
CAT |a POSPEL  |b 02  |c 20220629  |l MUB01  |h 0104 
CAT |a POSPEL  |b 02  |c 20221019  |l MUB01  |h 2326 
CAT |a POSPEL  |b 02  |c 20221101  |l MUB01  |h 0840 
CAT |a POSPEL  |b 02  |c 20230629  |l MUB01  |h 0037 
CAT |c 20240209  |l MUB01  |h 1158 
CAT |a POSPEL  |b 02  |c 20240405  |l MUB01  |h 2124 
CAT |a POSPEL  |b 02  |c 20240408  |l MUB01  |h 1014 
CAT |a VESELAX  |b 02  |c 20240516  |l MUB01  |h 1521 
CAT |a VESELAX  |b 02  |c 20240516  |l MUB01  |h 1522 
CAT |a VESELAX  |b 02  |c 20240516  |l MUB01  |h 1523 
CAT |a POSPEL  |b 02  |c 20241111  |l MUB01  |h 1100 
LOW |a POSLANO DO SKCR  |b 2016-12-16 
994 - 1 |l MUB01  |l MUB01  |m VYSPR  |1 FI  |a Fakulta informatiky  |3 Diz. práce 2016  |5 42005D2672  |8 20161201  |f 72  |f Týdenní  |r 20161201 
AVA |a INF50  |b FI  |d Diz. práce 2016  |e available  |t K dispozici  |f 1  |g 0  |h N  |i 1 

Podobné jednotky