Unrooted tree path lengths

Unrooted tree path lengths

In computer science, the problem of unrooted tree path lengths is that of finding the number of paths of each length in a tree.

It is known that no algorithm can solve it in less than O("n"2) asymptotic time.Fact|date=February 2008


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Binary tree — Not to be confused with B tree. A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at… …   Wikipedia

  • List of mathematics articles (U) — NOTOC U U duality U quadratic distribution U statistic UCT Mathematics Competition Ugly duckling theorem Ulam numbers Ulam spiral Ultraconnected space Ultrafilter Ultrafinitism Ultrahyperbolic wave equation Ultralimit Ultrametric space… …   Wikipedia

  • Distance matrices in phylogeny — Distance matrices are used in phylogeny as non parametric distance methods were originally applied to phenetic data using a matrix of pairwise distances. These distances are then reconciled to produce a tree (a phylogram, with informative branch… …   Wikipedia

  • Maximum parsimony — Maximum parsimony, often simply referred to as parsimony, is a non parametric statistical method commonly used in computational phylogenetics for estimating phylogenies. Under maximum parsimony, the preferred phylogenetic tree is the tree that… …   Wikipedia

  • Maximum parsimony (phylogenetics) — Parsimony is a non parametric statistical method commonly used in computational phylogenetics for estimating phylogenies. Under parsimony, the preferred phylogenetic tree is the tree that requires the least evolutionary change to explain some… …   Wikipedia

  • Quantitative comparative linguistics — is a branch of comparative linguistics that applies mathematical models to the problem of classifying language relatedness. This includes the use of computational phylogenetics and cladistics to define an optimal tree (or network) to represent a… …   Wikipedia

  • Top Trees — The Top Tree is a binary tree based data structure for unrooted dynamic trees which is used mainly for carrying out various path related operations, it allows simple Divide and conquer algorithms. It has since been augmented to maintain… …   Wikipedia

  • Least squares inference in phylogeny — generates a phylogenetic tree based on anobserved matrix of pairwise genetic distances andoptionally a weightmatrix. The goal is to find a tree which satisfies the distance constraints asbest as possible.Ordinary and weighted least squaresThe… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”