Consensus Algorithms for Trees and Strings
This thesis studies the computational complexity and polynomial-time approximability of a number of discrete combinatorial optimization problems involving labeled trees and strings. The problems considered have applications to computational molecular biology, pattern matching, and many other areas of computer science. The thesis is divided into three parts. In the first part, we study some proble