Practical verification of MSO properties of graphs of bounded clique width
33
pages
English
Documents
2010
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
33
pages
English
Documents
2010
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
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
Voir
- clique
- width properties
- graph properties
- properties like
- only ?
- free undirected graphs
- finite graphs
- graph theory
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)}
