Skip to main content

Computational study on branch decomposition of planar graphs

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2013-01-18
Authors/Contributors
Author: Zhu, Mingzhe
Abstract
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.
Document
Identifier
etd7640
Copyright statement
Copyright is held by the author.
Permissions
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Gu, Qianping
Member of collection
Download file Size
etd7640_MZhu.pdf 1.41 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 1