FO Model Checking of Interval Graphs (2013)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/13:00066379 |
|---|---|
| Název v anglickém jazyce | FO Model Checking of Interval Graphs |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2013 |
| 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 | 1 |
| 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: US - Spojené státy americké, 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 this problem can be solved in 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 some open subset, e.g., in the set (1, 1+epsilon). |
| Klíčová slova oddělená středníkem | interval graphs; first-order logic; parameterized complexity |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.1007/978-3-642-39212-2_24 |
Údaje o výsledku v závislosti na druhu výsledku
| Název sborníku | ICALP (2) 2013 |
|---|---|
| ISBN | 9783642392115 |
| ISSN | 0302-9743 |
| Počet stran výsledku | 13 |
| Strana od-do | 250-262 |
| Název nakladatele | Springer |
| Místo vydání | Berlin Heidelberg |
| Místo konání akce | Riga, Latvia |
| Datum konání akce | 2013 |
| Typ akce podle státní příslušnosti účastníků | WRD - Celosvětová |
| Kód UT WoS článku podle Web of Science | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | GA0 - Grantová agentura České republiky (GA ČR) |
| Rok sběru | 2014 |
| Specifikace | RIV/00216224:14330/13:00066379!RIV14-GA0-14330___ |
| Datum poslední aktualizace výsledku | 27.05.2014 |
| Kontrolní číslo | 56675947 |
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný GA ČR v programu GA | GAP202/11/0196 - Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů (2011 - 2013) |
|---|