Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-28T10:20:32.146Z Has data issue: false hasContentIssue false
  • English
  • Français

Inductive computations on graphs defined by clique-width expressions

Published online by Cambridge University Press:  04 April 2009

Frédérique Carrère
Frédérique Carrère*
Affiliation:
Laboratoire Bordelais de Recherche en Informatique, Université Bordeaux 1, CNRS, France. [email protected]
Get access

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) 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.

Keywords

Termsgraphsclique-widthlabeling schemesinductive computation.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 43 , Issue 3 , July 2009 , pp. 625 - 651
Copyright
© EDP Sciences, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arnborg, S., Lagergren, J., Seese, D., Easy problems for tree-decomposable graphs. J. Algor. 12 (1991) 308–340. CrossRef
Bodlaender, H., Treewidth: Algorithmic techniques and results, in Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science. Lect. Notes Comput. Sci. 1295 (1997) 19–36. CrossRef
R.B. Borie, R.G. Parker, C.A. Tovey, Algorithms on Recursively Constructed Graphs. CRC Handbook of Graph Theory (2003) 1046–1066.
Chaudhuri, S., Zaroliagis, C.D., Optimal parallel shortest paths in small treewidth digraphs, in: Proceedings 3rd Annual European Symposium on Algorithms. Lect. Notes Comput. Sci. 979 (1995) 31–45. CrossRef
Corneil, D.G., Habib, M., Lanlignel, J.M., Reed, B.A., Rotics, U., Polynomial time recognition algorithm of clique-width ≤ 3 graphs, LATIN'00. Lect. Notes Comput. Sci. 1776 (2000) 126–134. CrossRef
Courcelle, B., Clique-width of countable graphs: a compactness property. Discrete Math. 276 (2003) 127–148. CrossRef
Courcelle, B., Makowsky, J.A., Rotics, U., On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Appl. Math. 108 (2001) 23–52. CrossRef
Courcelle, B., Mosbah, M., Monadic second-order evaluations of tree-decomposable graphs. Theoret. Comput. Sci. 109 (1993) 49–82. CrossRef
Courcelle, B., Olariu, S., Upper bounds to clique-width of graphs. Discrete Appl. Math. 101 (2000) 77–114. CrossRef
Courcelle, B., Twigg, A., Compact forbidden-set routing, in: STACS'07 . Lect. Notes Comput. Sci. 4393 (2007) 37–48. CrossRef
Courcelle, B., Vanicat, R., Query efficient implementations of graphs of bounded clique-width. Discrete Appl. Math. 131 (2003) 129–150. CrossRef
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.
R.G. Downey, M.R. Fellows, Parametrized Complexity. Springer Verlag (1999).
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.
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.
J. Flum, M. Grohe, Theory of parametrized complexity. Springer Verlag (2006).
Frick, M., Grohe, M., The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130 (2004) 3–31. CrossRef
Gavoille, C., Katz, M., Nir A. Katz, C. Paul, D. Peleg, Approximate distance labeling schemes, ESA'01. Lect. Notes Comput. Sci. 2161 (2001) 476–488. CrossRef
Gavoille, C., Paul, C., Distance labeling scheme and split decomposition. Discrete Math. 273 (2003) 115–130. CrossRef
Gavoille, C., Peleg, D., Compact and localized distributed data structures. J. Distrib. Comput. 16 (2003) 111–120. CrossRef
Gavoille, C., Peleg, D., Pérennes, S., Raz, R., Distance labeling in graphs. J. Algor. 53 (2004) 85–112. CrossRef
Wanke, E., k-NLC graphs and polynomial algorithms. Disc. Appl. Math. 54 (1994) 251–266. CrossRef
Gurski, F., Wanke, E., Vertex disjoint paths on clique-width bounded graphs, LATIN'04. Lect. Notes Comput. Sci. 2978 (2004) 119–128. CrossRef
Harel, D., Tarjan, R., Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13 (1984) 338–355. CrossRef
Hlinený, P., Oum, S., Finding Branch-Decompositions and Rank-Decompositions. SIAM J. Comput. 38 (2008) 1012–1032. CrossRef
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.
J.P. Spinrad, Efficient Graph Representations. American Mathematical Society (2003).