Definitions and preliminaries Ehrenfeucht et al 's algorithm

Christophe Paul

Description

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

Sujets

• Algorithm
• Natural transformation
• Connected component
• Modular decomposition

Informations

• Publié par: pefav
• Nombre de lectures: 29
• Langue: English

Extrait

Definitions 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 DecompositionDefinitions 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 Montgolfier (LIAFA),
L. Viennot (INRIA Rocquencourt)
C. Paul Algorithmic Aspects of Modular DecompositionDefinitions 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 DecompositionDefinitions and preliminaries
Ehrenfeucht et al.’s algorithm
New algorithmic trends
1 Definitions 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)
Definitions 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 iff
∀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)
Definitions 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 iff
∀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 DecompositionDefinitions 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 iff
∀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
Definitions 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 DecompositionDefinitions 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.
Definitions 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