RAIRO-Theor. Inf. Appl.
Volume 43, Number 3, July-September 2009
|Page(s)||625 - 651|
|Published online||04 April 2009|
Inductive computations on graphs defined by clique-width expressions
Laboratoire Bordelais de Recherche en Informatique,
Université Bordeaux 1, CNRS, France. firstname.lastname@example.org
Accepted: 21 February 2009
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 D, if G is a graph with n vertices and of clique-width at most k, where k is fixed, we can associate with each vertex x of G a piece of information (bit sequence) lab(x) of length O(log2(n)) such that we can compute D in constant time, using only the labels of its arguments. The preprocessing can be done in time O(h.n) where h is the height of the syntactic tree of G. We perform an inductive computation, without using the tools of monadic second order logic. This enables us to give an explicit labelling scheme and to avoid constants of exponential size.
Mathematics Subject Classification: 68R10 / 90C35
Key words: Terms / graphs / clique-width / labeling schemes / inductive computation.
© EDP Sciences, 2009
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.