Submodular partition functions and duality treewidth bramble
88 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Submodular partition functions and duality treewidth bramble

-

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
88 Pages
English

Description

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 ...

Subjects

Informations

Published by
Reads 29
Language English

Exrait

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)tV(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)tV(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)tV(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