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

Métadonnées

Licence d’utilisation du document

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]

Langue

Article de revue

Ce document a été publié dans

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

Springer Verlag

Résumé en anglais

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.< Réduire

Mots clés en anglais

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

Project ANR

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

Origine

Importé de hal

Unités de recherche

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