Balanced vertices in trees and a simpler algorithm to compute the genomic distance
From MaRDI portal
Publication:607155
DOI10.1016/J.AML.2010.08.021zbMATH Open1213.05243arXiv1004.2735OpenAlexW1975475150MaRDI QIDQ607155FDOQ607155
Authors: Péter L. Erdős, Lajos Soukup, Jens Stoye 
Publication date: 19 November 2010
Published in: Applied Mathematics Letters (Search for Journal in Brave)
Abstract: 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 {it et al.} to compute the rearrangement distance between two multichromosomal genomes in linear time ({it Theor. Comput. Sci.}, 410:5300-5316, 2009). In the process it introduces a new {em center} notion for trees, which seems to be interesting on its own.
Full work available at URL: https://arxiv.org/abs/1004.2735
Recommendations
- Approximation algorithms for tree alignment with a given phylogeny
- A new balance index for phylogenetic trees
- On a matching distance between rooted phylogenetic trees
- scientific article; zbMATH DE number 2079368
- Computing the rooted triplet distance between phylogenetic networks
- Computing the rooted triplet distance between phylogenetic networks
- Aligning sequences via an evolutionary tree: complexity and approximation
- On distances in vertex-weighted trees
- On the complexity of computing MP distance between binary phylogenetic trees
Genetics and epigenetics (92D10) Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75)
Cites Work
Cited In (2)
This page was built for publication: Balanced vertices in trees and a simpler algorithm to compute the genomic distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607155)
