Compact labelings for efficient first-order model-checking

DOI10.1007/s10878-009-9260-7zbMath1237.90191arXiv0811.4713OpenAlexW2102621965MaRDI QIDQ626458

Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté

Publication date: 18 February 2011

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0811.4713

zbMATH Keywords

first-order logiclabeling schemelocal clique-widthlocal tree widthlocally bounded clique width

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (4)

Implicit representation of relations ⋮ On low rank-width colorings ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Fault-tolerant distance labeling for planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• Generalized model-checking over locally tree-decomposable classes
• Recent developments on graphs of bounded clique-width
• Arboricity and bipartite subgraph listing algorithms
• Query efficient implementation of graphs of bounded clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• On powers of graphs of bounded NLC-width (clique-width)
• Line graphs of bounded clique-width
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Approximating clique-width and branch-width
• Recognizability, hypergraph operations, and logical types
• Linear time low tree-width partitions and algorithmic consequences
• Deciding first-order properties of locally tree-decomposable structures
• Easy problems for tree-decomposable graphs
• Algorithmic Meta-theorems
• From Tree-Width to Clique-Width: Excluding a Unit Interval Graph
• First-order queries on structures of bounded degree are computable with constant delay
• Connectivity check in 3-connected planar graphs with obstacles
• Treewidth: Structure and Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Finding Branch-Decompositions and Rank-Decompositions

This page was built for publication: Compact labelings for efficient first-order model-checking