Efficient First-Order Model-Checking Using Short Labels

DOI10.1007/978-3-540-69311-6_18zbMath1143.68448OpenAlexW1554086393MaRDI QIDQ3507329

Mamadou Moustapha Kanté, Cyril Gavoille, Bruno Courcelle

Publication date: 19 June 2008

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69311-6_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60)

Cites Work

• Generalized model-checking over locally tree-decomposable classes
• Graph minors. V. Excluding a planar graph
• Query efficient implementation of graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Linear time low tree-width partitions and algorithmic consequences
• Deciding first-order properties of locally tree-decomposable structures
• Compact Forbidden-Set Routing
• Compact and localized distributed data structures
• First-order queries on structures of bounded degree are computable with constant delay
• Connectivity check in 3-connected planar graphs with obstacles
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Finding Branch-Decompositions and Rank-Decompositions
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient First-Order Model-Checking Using Short Labels