FO model checking of interval graphs

DOI10.2168/LMCS-11(4:11)2015MaRDI QIDQ3460413zbMATH OpenOpenAlexWikidataFDO

Authors Robert Ganian, Petr Hliněný, Jan Obdržálek, Jarett Schwartz, Jakub Teska, Daniel Král'

Publication date 7 January 2016

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/lmcs-11(4:11)2015

zbMATH Keywords

clique-widthparameterized complexityinterval graphfirst-order model checking

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• FO model checking of interval graphs
• Interval graph representation with given interval and intersection lengths
• FO model checking on geometric graphs
• FO model checking of geometric graphs

Cited in

(7)

• Recovering sparse graphs
• FO model checking on geometric graphs
• On the classes of interval graphs of limited nesting and count of lengths
• FO model checking of interval graphs
• FO model checking of geometric graphs
• Counting subgraphs in somewhere dense graphs
• Reducing CMSO model checking to highly connected graphs

This page was built for publication: FO model checking of interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460413)