Computational study on branch decomposition of planar graphs
Mingzhe Zhu · Summit (Simon Fraser University) · 2013
The notions of branchwidth and branch-decomposition of graphs are introduced by Robertson and Seymour and have important algorithmic applications. It is known that many NP-hard problems in a graph G admit efficient dynamic programming algorithms if G has a small branchwidth. These algorithms usually run in exponential time in the width of a given branch-decomposition of G and polynomial time in the size of G. So it is very important to decide the branchwidth and compute an optimal branch-decomposition of a given graph. It is NP-hard to compute an optimal branch-decomposition for general graphs. For a planar graph G, it is known that whether the branchwidth of G is at most a given integer can be decided in O(n2) time and an optimal branch-decomposition of G can be computed in O(n3) time. It is shown that the branchwidth and optimal branch-decomposition of a planar graph G can be computed efficiently in practice. In this thesis, heuristics are proposed to improve the practical efficiency of the O(n3) algorithm for the optimal branch-decomposition. Computational studies are conducted for the proposed heuristics and the results show that the practical performance of the O(n3) time algorithm can be improved significantly. The heuristics implemented provide efficient tools for computing the branchwidth and optimal branch-decomposition of planar graphs.