Practical algorithms for branch-decompositions of planar graphs

详细信息    查看全文

• 作者：Zhengbing Bian^a ; ^{zbian@dwavesys.com" class="auth_mail" title="E-mail the corresponding author} ; Qian-Ping Gu^b ; ^{qgu@sfu.ca" class="auth_mail" title="E-mail the corresponding author} ; Mingzhe Zhu^b ; ^{mingzhez@sfu.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph algorithms ; Branch-decomposition ; Planar graphs ; Computational study
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：30 January 2016
• 年：2016
• 卷：199
• 期：Complete
• 页码：156-171
• 全文大小：844 K

文摘

Branch-decompositions of graphs have important algorithmic applications. A graph 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G$G$ of small branchwidth admits efficient algorithms for many NP-hard problems in 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G$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$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$G$ and an integer β$\beta$, whether the branchwidth of 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G$G$ is at most β$\beta$ can be decided in a3552" title="Click to view the MathML source">O(n²)$O\left(n^2\right)$ time, and an optimal branch-decomposition of 52a33e4c7d748b292d9852ded68878c0" title="Click to view the MathML source">G$G$ can be computed in O(n³)$O\left(n^3\right)$ 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$G$ and the heuristics for improving the algorithms.