Computing branchwidth via efficient triangulations and blocks

International audienceMinimal triangulations and potential maximal cliques are the main ingredients for a number of polynomial time algorithms on different graph classes computing the treewidth of a graph. Potential maximal cliques are also the main engine of the fastest so far O(1.9601^n)-time exact treewidth algorithm. Based on the recent results of Mazoit, we define the structures that can be regarded as minimal triangulations and potential maximal cliques for branchwidth: efficient triangulations and blocks. We show how blocks can be used to construct an algorithm computing the branchwidth of a graph on n vertices in time (2+√3)^n · n^O(1)