Computational study on Bidimensionality Theory based algorithms

Resource type
Thesis type
((Thesis)) M.Sc.
Date created
Bidimensionality theory provides a general framework for developing subexponential fixed parameter algorithms for NP-hard problems. A representative example of such algorithms is the one for the longest path problem in planar graphs. The largest grid minor and the branch-decomposition of a graph play an important role in bidimensionality theory. The best known approximation algorithm for computing the largest grid minor of a planar graph has the approximation ratio 3. In this thesis, we report a computational study on a branch-decomposition based algorithm for the longest path problem in planar graphs. We implement the 3-approximation algorithm for computing large grid minors. We also design and implement an exact algorithm for computing the largest cylinder minor in planar graphs to evaluate the practical performance of the 3-approximation algorithm. The results show that the bidimensional framework is practical for the longest path problem in planar graphs.
Copyright statement
Copyright is held by the author.
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
Attachment Size
etd6757_CWang.pdf 520.82 KB