11:00
12:00

Séminaire BKB - Adrian Miclaus (Université de Bucarest)

Adrian Miclaus (Université de Bucarest)

Title: Faster algorithms for computing the hairpin completion distance and minimum ancestor

Abstract: In this paper we study two problems related to the hairpin completion.
The first problem asks the minimum number of hairpin operations necessary to transform one string into another, number that is called the hairpin completion distance.
For this problem we show an algorithm of running time O(n^2), where n is the maximum length of the two strings.
Our algorithm improves on the algorithm of Manea (TCS 2010), that has running time O(n^2 log n).
In the minimum distance common hairpin completion ancestor problem we want to find, for two input strings x and y, a string w that minimizes the sum of the hairpin completion distances to x and y. Similarly, we present an algorithm with running time O(n^2) that improves by a O(log n) factor the algorithm of Manea (TCS 2010).

English
salle 178, LaBRI