Inductive computations on graphs defined by clique-width expressions
Labelling problems for graphs consist in building distributed data structures, making it possible to check a given graph property or to compute a given function, the arguments of which are vertices. For an inductively computable function , if is a graph with vertices and of clique-width at most , where is fixed, we can associate with each vertex of a piece of information (bit sequence) lab(x) of length (log()) such that we can compute in constant time, using only the labels of its arguments....