COURCELLE, Bruno; GAVOILLE, Cyril; KANTÉ, Mamadou Moustapha

Metadatos

Licencia de uso del documento

COURCELLE, Bruno
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Institut universitaire de France [IUF]

GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

KANTÉ, Mamadou Moustapha
Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes [LIMOS]

Idioma

Article de revue

Este ítem está publicado en

Journal of Combinatorial Optimization. 2011-01-07, vol. 21, n° 1, p. 19--46

Springer Verlag

Resumen en inglés

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.< Leer menos

Palabras clave en inglés

First-Order Logic

Labeling Scheme

Local Clique-Width

Local Tree-Width

Locally Bounded Clique-Width.

Locally Bounded Clique-Width

URI

https://oskar-bordeaux.fr/handle/20.500.12278/198612

Proyecto ANR

Décompositions des graphes et algorithmes - ANR-06-BLAN-0148

Orígen

Importado de Hal

Centros de investigación

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800