Inductive computations on graphs defined by clique-width expressions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 625-651.

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) $\mathrm{lab}\left(x\right)$ of length $O\left({log}^{2}\left(n\right)\right)$ such that we can compute $D$ in constant time, using only the labels of its arguments. The preprocessing can be done in time $O\left(h.n\right)$ 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.

DOI : https://doi.org/10.1051/ita/2009010
Classification : 68R10,  90C35
Mots clés : terms, graphs, clique-width, labeling schemes, inductive computation
@article{ITA_2009__43_3_625_0,
author = {Carr\ere, Fr\'ed\'erique},
title = {Inductive computations on graphs defined by clique-width expressions},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {625--651},
publisher = {EDP-Sciences},
volume = {43},
number = {3},
year = {2009},
doi = {10.1051/ita/2009010},
zbl = {1176.68139},
mrnumber = {2541134},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2009010/}
}
TY  - JOUR
AU  - Carrère, Frédérique
TI  - Inductive computations on graphs defined by clique-width expressions
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
DA  - 2009///
SP  - 625
EP  - 651
VL  - 43
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2009010/
UR  - https://zbmath.org/?q=an%3A1176.68139
UR  - https://www.ams.org/mathscinet-getitem?mr=2541134
UR  - https://doi.org/10.1051/ita/2009010
DO  - 10.1051/ita/2009010
LA  - en
ID  - ITA_2009__43_3_625_0
ER  - 
Carrère, Frédérique. Inductive computations on graphs defined by clique-width expressions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 625-651. doi : 10.1051/ita/2009010. http://www.numdam.org/articles/10.1051/ita/2009010/`

[1] S. Arnborg, J. Lagergren, D. Seese, Easy problems for tree-decomposable graphs. J. Algor. 12 (1991) 308-340. | MR 1105479 | Zbl 0734.68073

[2] H. Bodlaender, Treewidth: Algorithmic techniques and results, in Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science. Lect. Notes Comput. Sci. 1295 (1997) 19-36. | MR 1640205 | Zbl 0941.05057

[3] R.B. Borie, R.G. Parker, C.A. Tovey, Algorithms on Recursively Constructed Graphs. CRC Handbook of Graph Theory (2003) 1046-1066.

[4] S. Chaudhuri, C.D. Zaroliagis, Optimal parallel shortest paths in small treewidth digraphs, in: Proceedings 3rd Annual European Symposium on Algorithms. Lect. Notes Comput. Sci. 979 (1995) 31-45. | MR 1460735

[5] D.G. Corneil, M. Habib, J.M. Lanlignel, B.A. Reed, U. Rotics, Polynomial time recognition algorithm of clique-width $\le 3$ graphs, LATIN'00. Lect. Notes Comput. Sci. 1776 (2000) 126-134. | Zbl 0961.05062

[6] B. Courcelle, Clique-width of countable graphs: a compactness property. Discrete Math. 276 (2003) 127-148. | MR 2046629 | Zbl 1073.68062

[7] B. Courcelle, J.A. Makowsky, U. Rotics, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Appl. Math. 108 (2001) 23-52. | MR 1804711 | Zbl 0972.05023

[8] B. Courcelle, M. Mosbah, Monadic second-order evaluations of tree-decomposable graphs. Theoret. Comput. Sci. 109 (1993) 49-82. | MR 1205621 | Zbl 0789.68083

[9] B. Courcelle, S. Olariu, Upper bounds to clique-width of graphs. Discrete Appl. Math. 101 (2000) 77-114. | MR 1743732 | Zbl 0958.05105

[10] B. Courcelle, A. Twigg, Compact forbidden-set routing, in: STACS'07. Lect. Notes Comput. Sci. 4393 (2007) 37-48. | MR 2361056

[11] B. Courcelle, R. Vanicat, Query efficient implementations of graphs of bounded clique-width. Discrete Appl. Math. 131 (2003) 129-150. | MR 2016489 | Zbl 1029.68113

[12] C. Demetrescu, G.F. Italiano, a new approach to dynamic all pairs shortest paths, in Proceedings of. the 35. th. Annual ACM Symposium on the Theory of Computing (2003) 159-166. | MR 2121050

[13] R.G. Downey, M.R. Fellows, Parametrized Complexity. Springer Verlag (1999).

[14] J. Engelfriet, G. Rozenberg, Node replacement graph grammars, in Handbook of Graph Grammars and Computing by Graph Transformation, Foundations, Vol. 1, edited by G. Rozenberg. World Scientific (1997) 1-94. | MR 1480953

[15] M.R. Fellows, F.A. Rosamond, U. Rotics, S. Szeider, Clique-width minimization is NP-hard. Proceedings of. the 38. th. Annual ACM Symposium on the Theory of Computing (2006) 354-362. | MR 2277161

[16] J. Flum, M. Grohe, Theory of parametrized complexity. Springer Verlag (2006). | MR 2238686

[17] M. Frick, M. Grohe, The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130 (2004) 3-31. | MR 2092847 | Zbl 1062.03032

[18] C. Gavoille, M. Katz, Nir A. Katz, C. Paul, D. Peleg, Approximate distance labeling schemes, ESA'01. Lect. Notes Comput. Sci. 2161 (2001) 476-488. | MR 1969938 | Zbl 1006.68542

[19] C. Gavoille, C. Paul, Distance labeling scheme and split decomposition. Discrete Math. 273 (2003) 115-130. | MR 2025945 | Zbl 1029.05136

[20] C. Gavoille, D. Peleg, Compact and localized distributed data structures. J. Distrib. Comput. 16 (2003) 111-120.

[21] C. Gavoille, D. Peleg, S. Pérennes, R. Raz, Distance labeling in graphs. J. Algor. 53 (2004) 85-112. | MR 2086610 | Zbl 1068.68104

[22] E. Wanke, $k$-NLC graphs and polynomial algorithms. Disc. Appl. Math. 54 (1994) 251-266. | MR 1300250 | Zbl 0812.68106

[23] F. Gurski, E. Wanke, Vertex disjoint paths on clique-width bounded graphs, LATIN'04. Lect. Notes Comput. Sci. 2978 (2004) 119-128. | MR 2095187

[24] D. Harel, R. Tarjan, Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13 (1984) 338-355. | MR 739994 | Zbl 0535.68022

[25] P. Hlinený, S. Oum, Finding Branch-Decompositions and Rank-Decompositions. SIAM J. Comput. 38 (2008) 1012-1032. | MR 2421076 | Zbl 1163.05331

[26] D. Seese, Interpretability and tree automata: A simple way to solve algorithmic problems on graphs closely related to trees, in Tree Automata and Languages, edited by M. Nivat, A. Podelski. North-Holland (1992) 83-114. | MR 1196733 | Zbl 0798.68059

[27] J.P. Spinrad, Efficient Graph Representations. American Mathematical Society (2003). | MR 1971502 | Zbl 1033.05001

Cité par Sources :