| Autor: |
Courcelle, Bruno, Gavoille, Cyril, Kanté, Mamadou Moustapha |
| Rok vydání: |
2008 |
| Předmět: |
|
| Zdroj: |
Journal of Combinatorial Optimisation 21(1):19-46(2011) |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1007/s10878-009-9260-7 |
| Popis: |
We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checking a first-order formula with free set variables in the graphs of every class that is \emph{nicely locally cwd-decomposable}. This notion generalizes that of a \emph{nicely locally tree-decomposable} class. The graphs of such classes can be covered by graphs of bounded \emph{clique-width} with limited overlaps. We also consider such labelings for \emph{bounded} first-order formulas on graph classes of \emph{bounded expansion}. Some of these results are extended to counting queries. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
