Computing branchwidth via efficient triangulations and blocks

Computing branchwidth via efficient triangulations and blocks

Jun 2005 | Fedor V. Fomin, Frédéric Mazoit, Ioan Todinca
This paper presents an efficient algorithm for computing the branchwidth of a graph. The authors introduce the concepts of efficient triangulations and blocks, which generalize the notions of minimal triangulations and potential maximal cliques used in treewidth computation. They show that blocks can be used to construct an algorithm that computes the branchwidth of a graph with n vertices in time $ (2 + \sqrt{3})^{n} \cdot n^{O(1)} $. Branchwidth is closely related to treewidth, with the two parameters differing by at most a factor of 1.5. While treewidth has been well-studied and efficient algorithms exist for its computation, branchwidth remains a challenging problem. The paper demonstrates that branchwidth can be computed using efficient triangulations and blocks, which allow for a more efficient algorithm than previously known methods. The algorithm is based on the concept of block-branchwidth, which is the branchwidth of a complete graph formed by a block of the original graph. The paper shows that the block-branchwidth of a block can be computed in $ \mathcal{O}^{*}(3^{s(B)}) $ time, where s(B) is the number of minimal separators bordering the block. This leads to an overall algorithm for computing the branchwidth of a graph in $ \mathcal{O}^{*}((2+\sqrt{3})^{n}) $ time and $ \mathcal{O}^{*}(2^{n}) $ space. The paper also discusses open problems, including the possibility of improving the efficiency of the block-branchwidth computation. It highlights the importance of efficient triangulations and blocks in the design of algorithms for branchwidth computation, and shows that these concepts can be used to develop a fast and effective algorithm for this problem.This paper presents an efficient algorithm for computing the branchwidth of a graph. The authors introduce the concepts of efficient triangulations and blocks, which generalize the notions of minimal triangulations and potential maximal cliques used in treewidth computation. They show that blocks can be used to construct an algorithm that computes the branchwidth of a graph with n vertices in time $ (2 + \sqrt{3})^{n} \cdot n^{O(1)} $. Branchwidth is closely related to treewidth, with the two parameters differing by at most a factor of 1.5. While treewidth has been well-studied and efficient algorithms exist for its computation, branchwidth remains a challenging problem. The paper demonstrates that branchwidth can be computed using efficient triangulations and blocks, which allow for a more efficient algorithm than previously known methods. The algorithm is based on the concept of block-branchwidth, which is the branchwidth of a complete graph formed by a block of the original graph. The paper shows that the block-branchwidth of a block can be computed in $ \mathcal{O}^{*}(3^{s(B)}) $ time, where s(B) is the number of minimal separators bordering the block. This leads to an overall algorithm for computing the branchwidth of a graph in $ \mathcal{O}^{*}((2+\sqrt{3})^{n}) $ time and $ \mathcal{O}^{*}(2^{n}) $ space. The paper also discusses open problems, including the possibility of improving the efficiency of the block-branchwidth computation. It highlights the importance of efficient triangulations and blocks in the design of algorithms for branchwidth computation, and shows that these concepts can be used to develop a fast and effective algorithm for this problem.
Reach us at info@study.space
Understanding Computing branchwidth via efficient triangulations and blocks