Cours MPRI 2009--2010 Treewidth II

Michel Habib [e-mail] ` `%%%`#_`__~~~False

Informations

• Publié par: Irnio
• Nombre de lectures: 13
• Langue: English

Extrait

Cours MPRI 2009–2010 Treewidth II
Cours MPRI 2009–2010
Treewidth II
Michel Habib
[e-mail]
http://www.liafa.jussieu.fr/~habib
Rue du chateau des rentiers, october 2009Other width parameters
Cliquewidth
Branchwidth and connectivity functions
Rankwidth
Some relationships between these widths
Cours MPRI 2009–2010 Treewidth II
Schedule
ExercisesCliquewidth
Branchwidth and connectivity functions
Rankwidth
Some relationships between these widths
Cours MPRI 2009–2010 Treewidth II
Schedule
Exercises
Other width parametersBranchwidth and connectivity functions
Rankwidth
Some relationships between these widths
Cours MPRI 2009–2010 Treewidth II
Schedule
Exercises
Other width parameters
CliquewidthRankwidth
Some relationships between these widths
Cours MPRI 2009–2010 Treewidth II
Schedule
Exercises
Other width parameters
Cliquewidth
Branchwidth and connectivity functionsSome relationships between these widths
Cours MPRI 2009–2010 Treewidth II
Schedule
Exercises
Other width parameters
Cliquewidth
Branchwidth and connectivity functions
RankwidthCours MPRI 2009–2010 Treewidth II
Schedule
Exercises
Other width parameters
Cliquewidth
Branchwidth and connectivity functions
Rankwidth
Some relationships between these widthsCours MPRI 2009–2010 Treewidth II
Exercises
Exercises
Other width parameters
Cliquewidth
Branchwidth and connectivity functions
Rankwidth
Some relationships between these widthsI Ptolemaic graphs are both chordal and distance-hereditary,
what are there characteristic elimination orderings?
Cours MPRI 2009–2010 Treewidth II
Exercises
I F. Dragan :
Consider the following elimination scheme :
delete a vertex of minimum degree in the remaining graph
Show that if G is chordal the end of this elimination ordering
is a clique of maximum size.Cours MPRI 2009–2010 Treewidth II
Exercises
I F. Dragan :
Consider the following elimination scheme :
delete a vertex of minimum degree in the remaining graph
Show that if G is chordal the end of this elimination ordering
is a clique of maximum size.
I Ptolemaic graphs are both chordal and distance-hereditary,
what are there characteristic elimination orderings?