The Library
FO model checking of interval graphs
Tools
Ganian, R., Hliněný, P., Král', Daniel, Obdržálek, J., Schwartz, J. and Teska, J. (2013) FO model checking of interval graphs. In: Freivalds, Rūsiņš and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , David, (eds.) Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II. Lecture Notes in Computer Science, Volume 7966 . Berlin ; London: Springer Berlin Heidelberg, pp. 250-262. ISBN 9783642392115
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-39212-2_24
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 logn) 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 + ε).
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Berlin Heidelberg | ||||
Place of Publication: | Berlin ; London | ||||
ISBN: | 9783642392115 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Automata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II | ||||
Editor: | Freivalds, Rūsiņš and Kwiatkowska, Martha and Fomin, Fedor V. and Peleg , David | ||||
Official Date: | 2013 | ||||
Dates: |
|
||||
Volume: | Volume 7966 | ||||
Page Range: | pp. 250-262 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Description: | |||||
Title of Event: | 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 | ||||
Type of Event: | Other | ||||
Location of Event: | Riga, Latvia | ||||
Date(s) of Event: | 8-12 July 2013 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |