Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Record link: 
http://hdl.handle.net/20.500.12708/54877
-
Title: 
FO Model Checking of Interval Graphs
-
Citation: 
Ganian, R., Hlinený, P., Král, D., Obdrálek, J., Schwartz, J., & Teska, J. (2013). FO Model Checking of Interval Graphs. In Automata, Languages, and Programming - 40th International Colloquium (pp. 250–262). Springer / LNCS. http://hdl.handle.net/20.500.12708/54877
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Authors: 
Ganian, Robert 
Hlinený, Petr 
Král, Daniel 
Obdrálek, Jan 
Schwartz, Jarett 
Teska, Jakub 
-
Organisational Unit: 
E192-03 - Forschungsbereich Knowledge Based Systems 
-
Published in: 
Automata, Languages, and Programming - 40th International Colloquium 
-
Date (published): 
2013
-
Event name: 
International Colloquium on Automata, Languages and Programming (ICALP) 
-
Event date: 
9-Jul-2012 - 13-Jul-2012
-
Event place: 
Warwick, UK, EU
-
Number of Pages: 
13
-
Publisher: 
Springer / LNCS, 7966
-
Peer reviewed: 
Yes
-
Keywords: 
parameterized complexity; FO model checking; interval graph; clique-width
-
Abstract: 
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).
en
Project title: 
The Parameterized Complexity of Reasoning Problems: 239962 (Europäischer Forschungsrat (ERC)) 
-
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
Mathematik, Informatik
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

182
checked on Nov 22, 2023

Google ScholarTM

Check