Practical verification of MSO properties of graphs of bounded clique width

pages

English

Documents

2010

Écrit par
Irène Durand

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

2010

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Publié le

01 octobre 2010

Nombre de lectures

Langue

English

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

Publié par

pefav

Publié le

01 octobre 2010

Nombre de lectures

Langue

English

Practical veriﬁcation 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 considerﬁnitegraphs only

Graphs as relational structures

3/33

For simplicity, we considersimple,loop-free undirectedgraphs Extensionsare easy Every graphGcan be identiﬁed with therelational structure (VGedgG) whereVGis the set of vertices andedgG⊆ VG× VG the binary symmetric relation that deﬁnes edges.

v7v6v2