Computational study on Bidimensionality Theory based algorithms

Author: 
Date created: 
2011-08-09
Identifier: 
etd6757
Keywords: 
Computational study
Bidimensionality theory
Branch-decomposition
Grid minor
Longest path problem
Abstract: 

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.

Document type: 
Thesis
Rights: 
Copyright remains with the author. The author granted permission for the file to be printed and for the text to be copied and pasted.
File(s): 
Senior supervisor: 
Qianping Gu
Department: 
Applied Science: School of Computing Science
Thesis type: 
((Computing Science) Thesis) M.Sc.
Statistics: