EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO-Theor. Inf. Appl.
Volume 43, Number 3, July-September 2009
Page(s) 625 - 651
DOI 10.1051/ita/2009010
Published online 04 April 2009

RAIRO-Theor. Inf. Appl. 43, 625-651 (2009)
DOI: 10.1051/ita/2009010

Inductive computations on graphs defined by clique-width expressions

Frédérique Carrère

Laboratoire Bordelais de Recherche en Informatique, Université Bordeaux 1, CNRS, France. carrere@labri.fr


Received June 25, 2007. Accepted February 21st, 2009. Published online 4 April 2009

Abstract
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) ${\rm lab}(x)$ of length $O(\log^2(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


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.