Name
Abstract | ||
|---|---|---|
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 nicely locally clique-width-decomposable. This notion generalizes that of a nicely locally tree-decomposable class. The graphs of such classes can be covered by graphs of bounded clique-width with limited overlaps. We also consider such labelings for bounded first-order formulas on graph classes of bounded expansion. Some of these results are extended to counting queries. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s10878-009-9260-7 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
First-order logic,Labeling scheme,Local clique-width,Local tree-width,Locally bounded clique-width | Journal | 21 |
Issue | ISSN | Citations |
1 | Journal of Combinatorial Optimisation 21(1):19-46(2011) | 0 |
PageRank | References | Authors |
0.34 | 22 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruno Courcelle | 1 | 3418 | 388.00 |
| Cyril Gavoille | 2 | 1526 | 114.20 |
| Mamadou Moustapha Kanté | 3 | 172 | 20.93 |