Detailed Information on Publication Record
2013
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 (840 United States of America), 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
Berlin Heidelberg, ICALP (2) 2013, p. 250-262, 13 pp. 2013
Publisher
Springer
Other information
Language
English
Type of outcome
Stať ve sborníku
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í
Publication form
printed version "print"
Impact factor
Impact factor: 0.402 in 2005
RIV identification code
RIV/00216224:14330/13:00066379
Organization unit
Faculty of Informatics
ISBN
978-3-642-39211-5
ISSN
UT WoS
000342684100024
Keywords in English
interval graphs; first-order logic; parameterized complexity
Tags
International impact, Reviewed
Změněno: 14/11/2014 13:23, 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 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).
Links
| GAP202/11/0196, research and development project |
|