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/ |
| Shrnutí: | 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 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 |
|---|---|
| Popis jednotky: | Vedoucí práce: Petr Hliněný |
| Fyzický popis: | viii, 104 stran, 16 listů : ilustrace |