文摘
Branch-decompositions of graphs have important algorithmic applications. A graph 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G of small branchwidth admits efficient algorithms for many NP-hard problems in 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G. These algorithms usually run in exponential time in the branchwidth and polynomial time in the size of 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G. It is critical to compute the branchwidth and a branch-decomposition of small width for a given graph in practical applications of these algorithms. It is known that given a planar graph 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G and an integer β, whether the branchwidth of 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G is at most β can be decided in a3552" title="Click to view the MathML source">O(n2) time, and an optimal branch-decomposition of 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G can be computed in O(n3) time. In this paper, we report the practical performance of the algorithms for computing the branchwidth/branch-decomposition of planar 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G and the heuristics for improving the algorithms.