Balanced Vertices in Trees and a Simpler Algorithm to Compute the Genomic Distance

Combinatorics Seminar
Thursday, October 28, 2010 - 2:00pm
1 hour (actually 50 minutes)
Skiles 269
Alfred Renyi Inst. of Mathematics, Budapest
In this talk we will report a short and transparent solution for the covering cost of white--grey trees which play a crucial role in the algorithm of Bergeron et al. to compute the rearrangement distance between two multi-chromosomal genomes in linear time (Theor. Comput. Sci., 410:5300-5316, 2009). In the process it introduces a new center notion for trees, which seems to be interesting on its own.