Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees

Details Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees

2001-01-26

arxiv.org/abs/cs/0101031v2

SIAM Journal on Computing, 30(2):602--624, 2000

Computer Science

Computational Engineering, Finance, and Science

Scientific paper

We present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n^{1.5} log n) time for trees with unbounded degrees, matching the best known time complexity for the rooted case. Our algorithm allows the input trees to be mixed trees, i.e., trees that may contain directed and undirected edges at the same time. Our algorithm adopts a recursive strategy exploiting a technique called label compression. The backbone of this technique is an algorithm that computes the maximum weight matchings over many subgraphs of a bipartite graph as fast as it takes to compute a single matching.

Affiliated with

Also associated with

No associations

Rating

Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees 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 Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-278181