Detailed Information on Publication Record
2015
FO Model Checking of Interval Graphs
GANIAN, Robert, Petr HLINĚNÝ, Daniel KRÁĽ, Jan OBDRŽÁLEK, Jarett SCHWARTZ et. al.Basic information
Original name
FO Model Checking of Interval Graphs
Authors
GANIAN, Robert (203 Czech Republic), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution), Daniel KRÁĽ (203 Czech Republic), Jan OBDRŽÁLEK (203 Czech Republic, belonging to the institution), Jarett SCHWARTZ (840 United States of America) and Jakub TESKA (203 Czech Republic)
Edition
Logical Methods in Computer Science, Německo, Logical Methods in Computer Science e.V. 2015, 1860-5974
Other information
Language
English
Type of outcome
Článek v odborném periodiku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Germany
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
Impact factor
Impact factor: 0.569
RIV identification code
RIV/00216224:14330/15:00081403
Organization unit
Faculty of Informatics
UT WoS
000373922900011
Keywords in English
rst-order model checking; parameterized complexity; interval graph; clique-width
Tags
Tags
International impact, Reviewed
Změněno: 14/2/2017 09:03, prof. RNDr. Petr Hliněný, Ph.D.
Abstract
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 FO model checking and successor-invariant FO model checking 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 an open subset, e.g., in the set (1, 1 + µ).
Links
| GA14-03501S, research and development project |
| ||
| MUNI/A/1159/2014, interní kód MU |
|