Discrete Mathematics and Optimization Seminar
Christophe Paul |
CNRS
Monday November 28th at 4.30pm
Burnside 1205
Title. New results on branchwidth
Abstract. The branchwidth, introduced in 92 by Roberston
and Seymour, is a connectivity parameter which is in general
NP-complete to compute. Unlike the treewidth, this parameter is
not up to now that well understood. Many results on branchwidth
only appear very recently. In this talk, we present two new results :
1) a simple and faster algorithm for the branchwidth of interval graphs; and
2) a characterization and algorithmic generation of maximal graph of branchwidth k,
called the k-branch.
The latter result can be seen as an analogous work to
the k-trees (edge maximal graph of treewidth k) studied by Arnborg and Proskurowski.