Título:  «Buscando un ciclo Euleriano compatible: un algoritmo rápido”
Directora: Verónica Becher
Jurados: Flavia Bonomo y Min Chih Lin

Resumen: Un ciclo Euleriano en un grafo G es un camino cerrado que usa todos los arcos de G exactamente una vez. Dos ciclos Eulerianos son compatibles si no comparten ningún camino de longitud 2. Fleischner y Jackson demuestran en 1990  que para todo camino Euleriano en un grafo dirigido de grado mínimo 3, existe otro ciclo Euleriano compatible. El resultado principal de esta tesis es un algoritmo para calcular un ciclo Euleriano compatible a uno dado en un grafo dirigido  de grado mínimo 3, con  complejidad de peor caso  O(E * log(V)) donde  V y E la cantidad de vértices y arcos del grafo. Nuestro algoritmo  se basa en las ideas de Lin, Ward, Jain y Skiena de 2011.     Un segundo resultado de esta tesis responde una pregunta de Becher y Heiber en 2011 y es un algoritmo para  extender una secuencia de  Bruijn de orden n a otra de orden n+1 para alfabetos de grado mayor o igual que 3.  Nuestra solución de este problema se basa en el algoritmo previamente descripto que genera un ciclo Euleriano compatible a otro dado. Esta solución también puede usarse para  extender  otras secuencias que son variantes de las secuencias de Bruijn, como los llamados collares perfectos.