//img.uscri.be/pth/99bc6bd08d201d1336f0da899553517059b34c0c
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Practical verification of MSO properties of graphs of bounded clique width

De
33 pages
Practical verification of MSO properties of graphs of bounded clique-width Irene Durand (joint work with Bruno Courcelle) LaBRI, Universite de Bordeaux 20 Octobre 2010 Decompositions de graphes, theorie, algorithmes et logiques, 2010

  • clique

  • width properties

  • graph properties

  • properties like

  • only ?

  • free undirected graphs

  • finite graphs

  • graph theory


Voir plus Voir moins
Practical verification of MSO properties of graphs of bounded clique-width
Ire`neDurand(jointworkwithBrunoCourcelle)
LaBRI,Universite´deBordeaux
20 Octobre 2010
D´ecompositionsdegraphes,the´orie,algorithmesetlogiques,2010
Objectives
/233
Verify properties of graphs of bounded clique-width
Properties connectedness, k-colorability, existence of cycles existence of paths bounds (cardinality, degree, . . . )    How: usingterm automata
Note that we considerfinitegraphs only
Graphs as relational structures
3/33
For simplicity, we considersimple,loop-free undirectedgraphs Extensionsare easy Every graphGcan be identified with therelational structure (VGedgG) whereVGis the set of vertices andedgG⊆ VG× VG the binary symmetric relation that defines edges.
v8
v7v6v2
v1
v3
v5v4 VG={v1v2v3v4v5v6v7v8} edgG={(v1v2)(v1v4)(v1v5)(v1v7)(v2v3)(v2v6)(v3v4)(v4v5)(v5v8)(v6v7)(v7v8)}