Definitions and preliminaries Ehrenfeucht et al 's algorithm

pages

English

Documents

Écrit par
Christophe Paul

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

Lire un extrait

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

Publié par

pefav

Nombre de lectures

Langue

English

Definitions and preliminaries Ehrenfeucht et al.'s algorithm New algorithmic trends Algorithmic Aspects of Modular Decomposition Christophe Paul CNRS - LIRMM - Univsersite Montpellier II, France October 24, 2006 Habilitation (in French) avalaible at C. Paul Algorithmic Aspects of Modular Decomposition

natural operation

principle computation

conquer paradigm

provide compact

connected components

modular decomposition

lirmm - univsersite montpellier

Voir

Publié par

pefav

Nombre de lectures

Langue

English

Deﬁnitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
Algorithmic Aspects of Modular Decomposition
Christophe Paul
CNRS - LIRMM - Univsersit´e Montpellier II, France
October 24, 2006
Habilitation (in French) avalaible at www.lirmm.fr/~paul
C. Paul Algorithmic Aspects of Modular DecompositionDeﬁnitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
Joint work with
B.M. Bui Xuan, C. Crespelle (LIRMM),
A. Bretscher, D. Corneil (U. of Toronto),
M. Habib, F. de Montgolﬁer (LIAFA),
L. Viennot (INRIA Rocquencourt)
C. Paul Algorithmic Aspects of Modular DecompositionDeﬁnitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
Some motivations
A very natural operation on discrete structures (used is the
proof of the perfect graph theorem)
Help to capture the structure of many graphs families (basis
of a theory for comparability graphs)
Divide and conquer paradigm for optimization problems
Provide compact representation of graphs (even for dynamic
graphs)
...
C. Paul Algorithmic Aspects of Modular DecompositionDeﬁnitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
1 Deﬁnitions and preliminaries
2 Ehrenfeucht et al.’s algorithm
Principle
Computation ofM(G,v)tion of MD(G )/M(G,v)
3 New algorithmic trends
Factoring permutation
LexBFS
C. Paul Algorithmic Aspects of Modular Decompositionconnected components
connected components of G
any vertex subset of the
complete graph (or the stable)
Deﬁnitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
Modules
A subset of vertices M of a graph G = (V,E) is a module iﬀ
∀x∈ V\M, either M⊆ N(x) or M∩N(x) =∅
Examples of modules2
6
1 4
7
3
C. Paul Algorithmic Aspects of Modular Decompositionany vertex subset of the
complete graph (or the stable)
Deﬁnitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
Modules
A subset of vertices M of a graph G = (V,E) is a module iﬀ
∀x∈ V\M, either M⊆ N(x) or M∩N(x) =∅
Examples of modules2
6 connected components
1 4 connected components of G
7
3
C. Paul Algorithmic Aspects of Modular DecompositionDeﬁnitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
Modules
A subset of vertices M of a graph G = (V,E) is a module iﬀ
∀x∈ V\M, either M⊆ N(x) or M∩N(x) =∅
Examples of modules2
6 connected components
1 4 connected components of G
any vertex subset of the
7
complete graph (or the stable)
3
C. Paul Algorithmic Aspects of Modular DecompositionLemma (Cournier, Ille 91)
If G is a prime graph, then any vertex but at most one belongs to
a P .4
Deﬁnitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
Prime graphs and degenerate graphs
A graph is prime is all its modules are trivial: e.g. the P .4
A graph is degenerate if any subset of vertices is a module:
cliques and stables.
C. Paul Algorithmic Aspects of Modular DecompositionDeﬁnitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
Prime graphs and degenerate graphs
A graph is prime is all its modules are trivial: e.g. the P .4
A graph is degenerate if any subset of vertices is a module:
cliques and stables.
Lemma (Cournier, Ille 91)
If G is a prime graph, then any vertex but at most one belongs to
a P .4
C. Paul Algorithmic Aspects of Modular DecompositionLemma
If x is a splitter for the set S, then
any module M containing S must
also contain x.
Deﬁnitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
Splitter
For a graph G = (V,E), the vertex x is a splitter for a set S of
vertices if∃y,z∈ S with xy∈ S and xz∈/ E. We say that x
separate y and z.
2
6
1 4
3
7
C. Paul Algorithmic Aspects of Modular Decomposition