Submodular partition functions and duality treewidth bramble
88
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
88
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Introduction Treewidth Partitions GeneralizationSubmodular partition functions and dualitytreewidth/bramble1 2 3Omid Amini Fr´ed´eric Mazoit Nicolas Nisse4St´ephan Thomass´e1Projet Mascotte, INRIA Sophia Antipolis.2LABRI, Universit´e Bordeaux.3LRI, Universit´e Paris-Sud.4LIRMM, Universit´e Montpellier II.S´eminaire ´equipe GraphComb, LRI, 25 mai 20071/33O. Amini, F. Mazoit, N. Nisse, S. Thomass´e Submodular partition functionsIntroduction Treewidth Partitions GeneralizationPlan1 Introduction2 Duality Theorem for Treewidth3 Partitions and Partition Functions4 Several duality theorems2/33O. Amini, F. Mazoit, N. Nisse, S. Thomass´e Submodular partition functionsIntroduction Treewidth Partitions GeneralizationMin-Max Theorem for several width parametersOur goalDuality treewidth/bramble [Seymour and Thomas 93]New proof of the min-max theorem for treewidthOur toolSubmodular partition functionsGeneralizationInterpretation of several width-parameters (treewidth,pathwidth, branchwidth, rankwidth, treewidth of matroid)in terms of submodular partition functions.3/33O. Amini, F. Mazoit, N. Nisse, S. Thomass´e Submodular partition functionsIntroduction Treewidth Partitions GeneralizationMin-Max Theorem for several width parametersOur goalDuality treewidth/bramble [Seymour and Thomas 93]New proof of the min-max theorem for treewidthOur toolSubmodular partition functionsGeneralizationInterpretation of several width-parameters (treewidth ...
Voir
Publié par
Langue
English
Introduction
Treewidth
Partitions
Generalization
Submodular partition functions treewidth/bramble
Omid
Amini1
Fre´de´ricMazoit2 St´ephanThomasse´4
and
Nicolas
1Projet Mascotte, INRIA Sophia Antipolis.
2IRU,LBArdea´eBorsitnive.xu
3isrevinU,IRL.ud-SisarePt´
4ptnoilleIIre.M,RMivUnsiereMt´LI
S´minaire´equipe e
GraphComb,
O.Amini,F.Mazoit,N.Nisse,S.Thomass´e
LRI,
25
mai
duality
Nisse3
Submodular partition functions
2007
1/33
Submodular partition functions
2/33
2
4
Several
duality
theorems
O.Amini,F.Mazoit,N.Nisse,S.Thomasse´
Functions
1
Introduction
Partitions
Generalization
Introduction Plan
Treewidth
Treewidth
Duality
Theorem
for
Partitions
3
Partition
and
IntroductionTreewidth Partitions Generalization Min-Max Theorem for several width parameters
Our goal Duality treewidth/bramble [Seymour and Thomas 93] New proof of the min-max theorem for treewidth
Our tool Submodular partition functions
Generalization Interpretation of several width-parameters (treewidth, pathwidth, branchwidth, rankwidth, treewidth of matroid) in terms of submodular partition functions.
O.Amini,F.Mazoit,N.Nisse,S.Thomasse´
Submodular partition functions
3/33
IntroductionTreewidth Partitions Generalization Min-Max Theorem for several width parameters
Our goal Duality treewidth/bramble [Seymour and Thomas 93] New proof of the min-max theorem for treewidth
Our tool Submodular partition functions
Generalization Interpretation of several width-parameters (treewidth, pathwidth, branchwidth, rankwidth, treewidth of matroid) in terms of submodular partition functions.
O.Amini,F.Mazoit,N.Nisse,S.Thomass´e
Submodular partition functions
3/33
IntroductionTreewidth Partitions Generalization Min-Max Theorem for several width parameters
Our goal Duality treewidth/bramble [Seymour and Thomas 93] New proof of the min-max theorem for treewidth
Our tool Submodular partition functions
Generalization Interpretation of several width-parameters (treewidth, pathwidth, branchwidth, rankwidth, treewidth of matroid) in terms of submodular partition functions.
O.Amini,F.Mazoit,N.Nisse,S.Thomasse´
Submodular partition functions
3/33
for
Theorem
3
Partitions
and
Partition
Functions
O.Amini,F.Mazoit,N.Nisse,S.Thomass´e
2
4
Several
duality
theorems
Duality
Treewidth
1
Introduction
Partitions
Generalization
Introduction Plan
Treewidth
Submodular partition functions
4/33
IntroductionTreewidth Tree decomp
ralization and
Partitions Gene osition
O.Amini,F.Mazoit,N.Nisse,S.Thomasse´
treewidth
Submodular partition functions
5/33
ralization and
IntroductionTreewidthPartitions Gene Tree decomposition
O. Amini, F. Mazoit, N. Nis , S. Tho ´ se masse
treewidth
a
tree
T
and
bags
Submodular partition functions
(Xt)t∈V(T)
5/33
IntroductionTreewidth Tree decomp
ralization and
Partitions Gene osition
O.Amini,F.Mazoit,N.Nisse,S.Thomass´e
treewidth
a
tree
T
and
bags
(
every vertex of least one bag;
Submodular partition functions
Xt G
)t i
∈V( s in
T) at
5/33
IntroductionTreewidth Tree decomp
ralization and
Partitions Gene osition
O.Amini,F.Mazoit,N.Nisse,S.Thomasse´
treewidth
a
tree
T
and
bags
(Xt)t∈V(T)
is in at least one
everyvertexofG bag; both ends of an edge of are in at least one same bag;
Submodular partition functions
G
5/33
IntroductionTreewidth Tree decomp
Partitions Gene osition
ralization and
O.Amini,F.Mazoit,N.Nisse,S.Thomass´e
treewidth
a
tree
T
and
bags
(Xt)t∈V(T)
is in at least one
everyvertexofG bag; both ends of anedgeofGare in at least one same bag; for any vertex ofG, all bags that contain it form a subtree.
Submodular partition functions
5/33
