The Library
FO model checking of interval graphs
Tools
Ganian, Robert, Hliněný, Petr , Králʼ, Daniel, Obdržálek, Jan, Schwartz, Jarett and Teska, Jakub (2015) FO model checking of interval graphs. Logical Methods in Computer Science, 11 (4). pp. 1-20. 11. doi:10.2168/LMCS-11(4:11)2015 ISSN 1860-5974.
|
PDF
WRAP_Kral_1302.6043.pdf - Published Version - Requires a PDF viewer. Available under License ["licenses_description_cc_by_nd_2" not defined]. Download (596Kb) | Preview |
|
PDF
WRAP_1173667-ma-110815-int-fo-journal-v2.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (232Kb) |
Official URL: http://dx.doi.org/10.2168/LMCS-11(4:11)2015
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 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 + ε).
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||
Library of Congress Subject Headings (LCSH): | Computer science -- Mathematics, Graph theory | ||||||
Journal or Publication Title: | Logical Methods in Computer Science | ||||||
Publisher: | International Federation for Computational Logic | ||||||
ISSN: | 1860-5974 | ||||||
Official Date: | December 2015 | ||||||
Dates: |
|
||||||
Volume: | 11 | ||||||
Number: | 4 | ||||||
Number of Pages: | 20 | ||||||
Page Range: | pp. 1-20 | ||||||
Article Number: | 11 | ||||||
DOI: | 10.2168/LMCS-11(4:11)2015 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 23 February 2016 | ||||||
Date of first compliant Open Access: | 23 February 2016 | ||||||
Funder: | European Research Council (ERC), Seventh Framework Programme (European Commission) (FP7), Fonds zur Förderung der Wissenschaftlichen Forschung (Austria) (FWF), Czech Science Foundation (CSF) | ||||||
Grant number: | 259385 (ERC), X-TRACT, P26696 (FWF), P202/11/0196 (CSF), 14-03501S (CSF) | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year