Structural and Geometric Graph Theory and Algorithmic Metatheorems /
Základním algoritmickým problémem v teorii konečných modelů je ověřování modelů na relačních strukturách. V současné době se aktivně zkoumá nalezení podtříd grafů, na kterých je ověřování modelů prvního řádu (FO) fixně parametricky tractabilní (FPT), protože ověřování FO modelů na obecných grafech j...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2024
|
| Témata: | |
| On-line přístup: | https://is.muni.cz/th/figrc/ |
| LEADER | 04323ctm a22005417i 4500 | ||
|---|---|---|---|
| 001 | MUB01006546292 | ||
| 003 | CZ BrMU | ||
| 005 | 20250409174813.0 | ||
| 008 | 241109s2024 xr ||||| |||||||||||eng d | ||
| 035 | |a (ISMU-VSKP)349673 | ||
| 040 | |a BOD114 |b cze |d BOD018 |e rda | ||
| 072 | 7 | |a 004.4/.6 |x Programování. Software |2 Konspekt |9 23 | |
| 080 | |a 004.421 |2 MRF | ||
| 080 | |a 517.18(084.21) |2 MRF | ||
| 080 | |a 004.94 |2 MRF | ||
| 100 | 1 | |a Pokrývka, Filip |% UČO 433705 |* [absolvent FI MU] |4 dis | |
| 242 | 1 | 0 | |a Structural and Geometric Graph Theory and Algorithmic Metatheorems |y eng |
| 245 | 1 | 0 | |a Structural and Geometric Graph Theory and Algorithmic Metatheorems / |c Filip Pokrývka |
| 264 | 0 | |c 2024 | |
| 300 | |a viii, 104 stran, 16 listů : |b ilustrace | ||
| 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, 2024 | ||
| 520 | 2 | |a Základním algoritmickým problémem v teorii konečných modelů je ověřování modelů na relačních strukturách. V současné době se aktivně zkoumá nalezení podtříd grafů, na kterých je ověřování modelů prvního řádu (FO) fixně parametricky tractabilní (FPT), protože ověřování FO modelů na obecných grafech je AW[*]-těžké. Zaměřujeme se na složitost ověřování FO modelů různých tříd průnikových grafů (intervalové grafy, permutační grafy, kruhové grafy) a zkoumáme podtřídy, kde je ověřování FO modelů efektivně vypočitatelné, tj. připouští FPT algoritmus. Bonnet a kol. nedávno zavedli grafový parametr dvojičková šířka a poskytli FPT algoritmus pro ověřování FO modelů na třídách grafů s omezenou dvojičkovou šířkou. Existují příklady tříd grafů, kde dvojičková šířka určuje hranici mezi tractabilním a netractabilním ověřováním FO modelů na dědičných podtřídách. Jedním takovým příkladem je třída permutačních grafů, ke které přidáváme kruhové grafy a intervalové grafy. Problém splnitelnosti CNF formul |% cze | |
| 520 | 2 | 9 | |a A fundamental algorithmic problem in finite model theory is model checking on relational structures. A currently active area of research focuses on finding graph subclasses on which first-order (FO) model checking is fixed-parameter tractable (FPT), since FO model checking on general graphs is AW[*]-hard. We focus on the complexity of FO model checking of various intersection graph classes (interval graphs, permutation graphs, circle graphs), and study the subclasses where FO model checking is computable efficiently, i.e. admits an FPT algorithm. Bonnet et al. recently introduced the graph parameter twin-width and provided an FPT algorithm for FO model checking on graph classes of bounded twin-width. There are examples of graph classes where twin-width defines the border between tractable and intractable FO model checking on hereditary subclasses. One such example is the class of permutation graphs, and we add circle graphs and interval graphs to the list. Satisfiability problem of C |9 eng |
| 650 | 0 | 7 | |a algoritmy (programování) |7 ph131788 |2 czenas |
| 650 | 0 | 7 | |a grafy funkcí |7 ph946128 |2 czenas |
| 650 | 0 | 7 | |a počítačové modelování |7 ph124513 |2 czenas |
| 650 | 0 | 9 | |a computer algorithms |2 eczenas |
| 650 | 0 | 9 | |a graphs of functions |2 eczenas |
| 650 | 0 | 9 | |a computer modeling |2 eczenas |
| 655 | 7 | |a disertace |7 fd132024 |2 czenas | |
| 655 | 9 | |a dissertations |2 eczenas | |
| 658 | |a Informatika |b Fundamenty informatiky |c FI D-INF DIFI (DIFI) |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 https://is.muni.cz/th/figrc/ |
| CAT | |c 20241109 |l MUB01 |h 0422 | ||
| CAT | |a POSPEL |b 02 |c 20241111 |l MUB01 |h 1100 | ||
| CAT | |a HANAV |b 02 |c 20241121 |l MUB01 |h 1108 | ||
| CAT | |a VESELA |b 02 |c 20250331 |l MUB01 |h 1448 | ||
| CAT | |a VESELA |b 02 |c 20250408 |l MUB01 |h 1229 | ||
| CAT | |a HANAV |b 02 |c 20250409 |l MUB01 |h 1748 | ||
| 994 | - | 1 | |l MUB01 |l MUB01 |m VYSPR |1 FI |a Fakulta informatiky |3 Diz. práce 2024 |5 42005D2781 |8 20250331 |f 72 |f Týdenní |r 20250331 |
| AVA | |a INF50 |b FI |d Diz. práce 2024 |e available |t K dispozici |f 1 |g 0 |h N |i 0 | ||