FO Model Checking of Interval Graphs (2015)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/15:00081403 |
|---|---|
| Název v anglickém jazyce | FO Model Checking of Interval Graphs |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2015 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku | 2 |
| Počet tvůrců celkem | 6 |
| Počet domácích tvůrců | 2 |
| Výčet všech uvedených jednotlivých tvůrců | Robert Ganian (státní příslušnost: CZ - Česká republika, vedidk: 6376290) Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646) Daniel Kráľ (státní příslušnost: CZ - Česká republika) Jan Obdržálek (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 3294099) Jarett Schwartz (státní příslušnost: US - Spojené státy americké) Jakub Teska (státní příslušnost: CZ - Česká republika) |
| Popis výsledku v anglickém jazyce | We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that FO model checking and successor-invariant FO model checking can be solvedin time O(n log n) for n-vertex interval graphs with representations containing only intervals with lengths from a prescribed finite set. We complement this result by showing that the same is not true if the lengths are restricted to any set that is dense in an open subset, e.g., in the set (1, 1 + ?). |
| Klíčová slova oddělená středníkem | rst-order model checking; parameterized complexity; interval graph; clique-width |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.2168/LMCS-11(4:11)2015 |
Údaje o výsledku v závislosti na druhu výsledku
| Název periodika | Logical Methods in Computer Science |
|---|---|
| ISSN | 1860-5974 |
| Svazek periodika | 11 |
| Číslo periodika v rámci uvedeného svazku | 4:11 |
| Stát vydavatele periodika | DE - Spolková republika Německo |
| Počet stran výsledku | 20 |
| Strana od-do | 1-20 |
| Kód UT WoS článku podle Web of Science | - |
| EID výsledku v databázi Scopus | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | MSM - Ministerstvo školství, mládeže a tělovýchovy (MŠMT) |
| Rok sběru | 2016 |
| Specifikace | RIV/00216224:14330/15:00081403!RIV16-MSM-14330___ |
| Datum poslední aktualizace výsledku | 24.05.2016 |
| Kontrolní číslo | 191636625 |
Informace o dalších výskytech výsledku dodaného stejným předkladatelem
| Dodáno GA ČR v roce 2016 | RIV/00216224:14330/15:00081403 v dodávce dat RIV16-GA0-14330___/01:1 |
|---|
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný GA ČR v programu GA | GA14-03501S - Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky (2014 - 2016) |
|---|---|
| Podpora / návaznosti | Specifický výzkum na vysokých školách, poskytovatel MŠMT |