Exact and approximation algorithms for graph problems with some biological applications
(2009) Abstract
 In this thesis we study several combinatorial problems in algorithmic graph theory and computational biology, and different algorithmical approaches for solving them.
In particular, we focus on graph algorithms, seeking for the most part polynomial or subexponential exact solutions, but in some cases also approximate solutions.
In the first part we study two problems on phylogenetic trees, the problem of finding a consensus tree for a set of phylogenetic trees, and the problem of combining a set of not necessarily consistent threetaxon trees into a phylogenetic tree that represents the input trees as closely as possible.
The second part is devoted to the problem of the embedding of graphs into integer lattices.... (More)  In this thesis we study several combinatorial problems in algorithmic graph theory and computational biology, and different algorithmical approaches for solving them.
In particular, we focus on graph algorithms, seeking for the most part polynomial or subexponential exact solutions, but in some cases also approximate solutions.
In the first part we study two problems on phylogenetic trees, the problem of finding a consensus tree for a set of phylogenetic trees, and the problem of combining a set of not necessarily consistent threetaxon trees into a phylogenetic tree that represents the input trees as closely as possible.
The second part is devoted to the problem of the embedding of graphs into integer lattices. In particular, we extend the problem to integer lattices of higher dimensions. We present a subexponentialtime method for optimal embedding of an arbitrary graph into a ddimensional integer lattice. In particular, it yields a subexponentialtime algorithm for optimal protein folding in the HPmodel.
Next, we study the problem of efficiently finding shortest cycles, and present approximation algorithms for both the weighted and unweighted variants of this problem.
Finally, we consider the approximability of the maximum and minimum edge clique partition problems, giving upper and lower bounds, and present approximation algorithms for both variants. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1390503
 author
 Lundell, EvaMarta ^{LU}
 supervisor

 Andrzej Lingas ^{LU}
 opponent

 Professor Heggernes, Pinar, Institutt for Informatikk, Universitetet i Bergen, Norway
 organization
 publishing date
 2009
 type
 Thesis
 publication status
 published
 subject
 keywords
 Graph algorithms, computational biology, approximation algorithms, computational complexity, evolutionary trees, maximum agreement subtree, graph embedding, shortest cycle, clique partitioning
 pages
 92 pages
 defense location
 E:1406, Ebuilding, Ole Römers väg 3
 defense date
 20090520 13:00:00
 ISBN
 9789162877859
 language
 English
 LU publication?
 yes
 id
 3ac9524a89fc40bc9b395b50884d3287 (old id 1390503)
 date added to LUP
 20160404 09:38:21
 date last changed
 20181121 20:54:31
@phdthesis{3ac9524a89fc40bc9b395b50884d3287, abstract = {{In this thesis we study several combinatorial problems in algorithmic graph theory and computational biology, and different algorithmical approaches for solving them.<br/><br> In particular, we focus on graph algorithms, seeking for the most part polynomial or subexponential exact solutions, but in some cases also approximate solutions.<br/><br> In the first part we study two problems on phylogenetic trees, the problem of finding a consensus tree for a set of phylogenetic trees, and the problem of combining a set of not necessarily consistent threetaxon trees into a phylogenetic tree that represents the input trees as closely as possible.<br/><br> The second part is devoted to the problem of the embedding of graphs into integer lattices. In particular, we extend the problem to integer lattices of higher dimensions. We present a subexponentialtime method for optimal embedding of an arbitrary graph into a ddimensional integer lattice. In particular, it yields a subexponentialtime algorithm for optimal protein folding in the HPmodel.<br/><br> Next, we study the problem of efficiently finding shortest cycles, and present approximation algorithms for both the weighted and unweighted variants of this problem.<br/><br> Finally, we consider the approximability of the maximum and minimum edge clique partition problems, giving upper and lower bounds, and present approximation algorithms for both variants.}}, author = {{Lundell, EvaMarta}}, isbn = {{9789162877859}}, keywords = {{Graph algorithms; computational biology; approximation algorithms; computational complexity; evolutionary trees; maximum agreement subtree; graph embedding; shortest cycle; clique partitioning}}, language = {{eng}}, school = {{Lund University}}, title = {{Exact and approximation algorithms for graph problems with some biological applications}}, year = {{2009}}, }