𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Balanced vertices in trees and a simpler algorithm to compute the genomic distance

✍ Scribed by Péter L. Erdős; Lajos Soukup; Jens Stoye

Book ID
104000970
Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
218 KB
Volume
24
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

This paper provides 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 multichromosomal genomes in linear time (A. Bergeron, J. Mixtacki, J. Stoye, A new linear time algorithm to compute the genomic distance via the double cut and join distance, Theor. Comput. Sci. 410 (2009) 5300-5316). In the process it introduces a new center notion for trees, which seems to be interesting on its own.

📜 SIMILAR VOLUMES

[Lecture Notes in Computer Science] Algo
[Lecture Notes in Computer Science] Algorithms and Computation Volume 1741 || Constructing the Suffix Tree of a Tree with a Large Alphabet
✍ Shibuya, Tetsuo 📂 Article 📅 1999 🏛 Springer Berlin Heidelberg 🌐 German ⚖ 176 KB

This book constitutes the refereed proceedings of the 10th International Symposium on Algorithms and Computation, ISAAC'99, held in Chennai, India, in December 1999. The 40 revised full papers presented together with four invited contributions were carefully reviewed and selected from 71 submissio