Thesis Topic Details

Topic ID:
3457
Title:
Parameterized Algorithm for k-Leaf Spanning Tree
Supervisor:
Serge Gaspers
Research Area:
Algorithms, Theory, Discrete Mathematics
Associated Staff
Assessor:
Aleksandar Ignjatovic
Topic Details
Status:
Active
Type:
Research
Programs:
CS CE BIOM BINF SE
Group Suitable:
No
Industrial:
No
Pre-requisites:
--
Description:
In the k-Leaf Spanning Tree problem (k-LST), the input is a graph G on n vertices and an integer k, and the question is whether G has a spanning tree with at least k leafs. k-LST is NP-complete and has applications in communication network design, circuit layouts, and distributed systems. With respect to the parameter k, the current fastest algorithm for this problem has running time 3.72^k*poly(n) [http://arxiv.org/abs/0810.4946].

The goal of this project is to design a faster algorithm for k-LST by analyzing the No-instances for small values of k (compared to n).
Comments:
--
Past Student Reports
 
No Reports Available. Contact the supervisor for more information.

Check out all available reports in the CSE Thesis Report Library.

NOTE: only current CSE students can login to view and select reports to download.