Affine and Projective Tree Metric Theorems

Details Affine and Projective Tree Metric Theorems Affine and Projective Tree Metric Theorems

2011-03-11

arxiv.org/abs/1103.2384v2

Mathematics

Combinatorics

Scientific paper

The tree metric theorem provides a combinatorial four point condition that characterizes dissimilarity maps derived from pairwise compatible split systems. A similar (but weaker) four point condition characterizes dissimilarity maps derived from circular split systems (Kalmanson metrics). The tree metric theorem was first discovered in the context of phylogenetics and forms the basis of many tree reconstruction algorithms, whereas Kalmanson metrics were first considered by computer scientists, and are notable in that they are a non-trivial class of metrics for which the traveling salesman problem is tractable. We present a unifying framework for these theorems based on combinatorial structures that are used for graph planarity testing. These are (projective) PC-trees, and their affine analogs, PQ-trees. In the projective case, we generalize a number of concepts from clustering theory, including hierarchies, pyramids, ultrametrics and Robinsonian matrices, and the theorems that relate them. As with tree metrics and ultrametrics, the link between PC-trees and PQ-trees is established via the Gromov product.

Affiliated with

Also associated with

No associations

Rating

Affine and Projective Tree Metric Theorems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Affine and Projective Tree Metric Theorems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Affine and Projective Tree Metric Theorems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-278152