Inductive computations on graphs defined by clique-width expressions

Frédérique Carrère

RAIRO - Theoretical Informatics and Applications (2009)

  • Volume: 43, Issue: 3, page 625-651
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Carrère, Frédérique. "Inductive computations on graphs defined by clique-width expressions." RAIRO - Theoretical Informatics and Applications 43.3 (2009): 625-651. <http://eudml.org/doc/250600>.

@article{Carrère2009,
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. },
author = {Carrère, Frédérique},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Terms; graphs; clique-width; labeling schemes; inductive computation.; terms; inductive computation},
language = {eng},
month = {4},
number = {3},
pages = {625-651},
publisher = {EDP Sciences},
title = {Inductive computations on graphs defined by clique-width expressions},
url = {http://eudml.org/doc/250600},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Carrère, Frédérique
TI - Inductive computations on graphs defined by clique-width expressions
JO - RAIRO - Theoretical Informatics and Applications
DA - 2009/4//
PB - EDP Sciences
VL - 43
IS - 3
SP - 625
EP - 651
AB - 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.
LA - eng
KW - Terms; graphs; clique-width; labeling schemes; inductive computation.; terms; inductive computation
UR - http://eudml.org/doc/250600
ER -

References

top
  1. S. Arnborg, J. Lagergren, D. Seese, Easy problems for tree-decomposable graphs. J. Algor.12 (1991) 308–340.  Zbl0734.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.  Zbl0941.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.  
  5. D.G. Corneil, M. Habib, J.M. Lanlignel, B.A. Reed, U. Rotics, Polynomial time recognition algorithm of clique-width ≤ 3 graphs, LATIN'00. Lect. Notes Comput. Sci. 1776 (2000) 126–134.  
  6. B. Courcelle, Clique-width of countable graphs: a compactness property. Discrete Math.276 (2003) 127–148.  Zbl1073.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.  Zbl0972.05023
  8. B. Courcelle, M. Mosbah, Monadic second-order evaluations of tree-decomposable graphs. Theoret. Comput. Sci.109 (1993) 49–82.  Zbl0789.68083
  9. B. Courcelle, S. Olariu, Upper bounds to clique-width of graphs. Discrete Appl. Math.101 (2000) 77–114.  Zbl0958.05105
  10. B. Courcelle, A. Twigg, Compact forbidden-set routing, in: STACS'07 . Lect. Notes Comput. Sci. 4393 (2007) 37–48.  Zbl1186.68331
  11. B. Courcelle, R. Vanicat, Query efficient implementations of graphs of bounded clique-width. Discrete Appl. Math.131 (2003) 129–150.  Zbl1029.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.  Zbl1192.90223
  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.  
  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.  Zbl1301.68145
  16. J. Flum, M. Grohe, Theory of parametrized complexity. Springer Verlag (2006).  Zbl1143.68016
  17. M. Frick, M. Grohe, The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic130 (2004) 3–31.  Zbl1062.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.  Zbl1006.68542
  19. C. Gavoille, C. Paul, Distance labeling scheme and split decomposition. Discrete Math.273 (2003) 115–130.  Zbl1029.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.  Zbl1068.68104
  22. E. Wanke, k-NLC graphs and polynomial algorithms. Disc. Appl. Math.54 (1994) 251–266.  Zbl0812.68106
  23. F. Gurski, E. Wanke, Vertex disjoint paths on clique-width bounded graphs, LATIN'04. Lect. Notes Comput. Sci.2978 (2004) 119–128.  Zbl1196.68173
  24. D. Harel, R. Tarjan, Fast algorithms for finding nearest common ancestors. SIAM J. Comput.13 (1984) 338–355.  Zbl0535.68022
  25. P. Hlinený, S. Oum, Finding Branch-Decompositions and Rank-Decompositions. SIAM J. Comput.38 (2008) 1012–1032.  Zbl1163.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.  Zbl0798.68059
  27. J.P. Spinrad, Efficient Graph Representations. American Mathematical Society (2003).  Zbl1033.05001

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.