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-widthfirst-order model checkinginterval graphparameterized complexity

Mathematics Subject Classification ID

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

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

(9)

• FO model checking on geometric graphs
• On the classes of interval graphs of limited nesting and count of lengths
• Reducing CMSO model checking to highly connected graphs
• Recovering sparse graphs
• FO model checking of geometric graphs
• FO model checking of interval graphs
• Counting subgraphs in somewhere dense graphs
• Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms
• On algorithmic applications of \(\mathcal{F}\)-branchwidth

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)