Submodular partition functions and duality treewidth bramble

Omid Amini, Frédéric Mazoit, =1=Nicolas Nisse, Stéphan Thomassé

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

Informations

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

Extrait

Introduction

Treewidth

Partitions

Generalization

Submodular partition functions treewidth/bramble

Omid

Amini 1

Fre´de´ricMazoit 2 St´ephanThomasse´ 4

and

Nicolas

1 Projet Mascotte, INRIA Sophia Antipolis.

2 IRU,LBArdea´eBorsitnive.xu

3 isrevinU,IRL.ud-SisarePt´

4 ptnoilleIIre.M,RMivUnsiereMt´LI

S´minaire´equipe e

GraphComb,

O.Amini,F.Mazoit,N.Nisse,S.Thomass´e

LRI,

25

mai

duality

Nisse 3

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

(X t ) 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

X t 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

(X t ) 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

(X t ) 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