Discrete Mathematics and Optimization Seminar

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