2013
FO Model Checking of Interval Graphs
GANIAN, Robert, Petr HLINĚNÝ, Daniel KRÁĽ, Jan OBDRŽÁLEK, Jarett SCHWARTZ et. al.Základní údaje
Originální název
FO Model Checking of Interval Graphs
Autoři
GANIAN, Robert (840 Spojené státy), Petr HLINĚNÝ (203 Česká republika, garant, domácí), Daniel KRÁĽ (203 Česká republika), Jan OBDRŽÁLEK (203 Česká republika, domácí), Jarett SCHWARTZ (840 Spojené státy) a Jakub TESKA (203 Česká republika)
Vydání
Berlin Heidelberg, ICALP (2) 2013, od s. 250-262, 13 s. 2013
Nakladatel
Springer
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14330/13:00066379
Organizační jednotka
Fakulta informatiky
ISBN
978-3-642-39211-5
ISSN
UT WoS
000342684100024
Klíčová slova anglicky
interval graphs; first-order logic; parameterized complexity
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 14. 11. 2014 13:23, prof. RNDr. Petr Hliněný, Ph.D.
Anotace
V originále
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).
Návaznosti
| GAP202/11/0196, projekt VaV |
|