Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees

2001/01/27 by Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1
Computer Science · #cs.CE #cs.DS

paper · pdf

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

arxiv created 2001/01/27 · arxiv updated 2009/11/30

Abstract

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.

Related

• Tree Contractions and Evolutionary Trees
• An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings
• Largest Weight Common Subtree Embeddings with Distance Penalties
• Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests
• Relaxed Agreement Forests