Abstract
In this thesis three general problems concerning construction of evolutionary trees are considered. Algorithms for the problems are presented and the complexity of the problems is investigated.
The thesis consists of three corresponding parts. The first part is devoted to the problem of constructing evolutionary trees in the experiment model. Different algorithms for the problem are given, including an optimal algorithm for constructing evolutionary trees and an optimal algorithm for merging two evolutionary trees. Matching lower bounds are also provided.
The second part of the thesis presents results related to the inferred consensus tree problem. The optimization version of the problem is shown to be NPcomplete and two heuristic algorithms are presented. Further, the ordered version of the problem is studied.
In the last part of the thesis the complexity of the maximum homeomorphic subtree problem is examined. The problem is shown to be hard to approximate, unless P=NP, even for trees of constant height, whereas a constant approximation ratio is obtained in case of a constant number of trees of constant height.
The thesis consists of three corresponding parts. The first part is devoted to the problem of constructing evolutionary trees in the experiment model. Different algorithms for the problem are given, including an optimal algorithm for constructing evolutionary trees and an optimal algorithm for merging two evolutionary trees. Matching lower bounds are also provided.
The second part of the thesis presents results related to the inferred consensus tree problem. The optimization version of the problem is shown to be NPcomplete and two heuristic algorithms are presented. Further, the ordered version of the problem is studied.
In the last part of the thesis the complexity of the maximum homeomorphic subtree problem is examined. The problem is shown to be hard to approximate, unless P=NP, even for trees of constant height, whereas a constant approximation ratio is obtained in case of a constant number of trees of constant height.
Original language  English 

Qualification  Doctor 
Awarding Institution  
Supervisors/Advisors 

Award date  2001 Jun 1 
Publisher  
ISBN (Print)  9162847724 
Publication status  Published  2001 
Bibliographical note
Defence detailsDate: 20010601
Time: 10:15
Place: Building E at LTH, Room E:B
External reviewer(s)
Name: Halldorsson, Magnus
Title: [unknown]
Affiliation: [unknown]

Subject classification (UKÄ)
 Computer Science
Free keywords
 Computer science
 Maximum homeomorphic subtrees
 Consensus trees
 Experiment model
 Evolutionary trees
 Complexity
 Computational biology
 Algorithms
 Data structures
 numerical analysis
 systems
 control
 Datalogi
 numerisk analys
 system
 kontroll
 Biology
 Biologi