3 papers
cs.CE2001
Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees
Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1
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…
cs.CV2001
An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings
Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1
A widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure is onl…
cs.DS2000
A Decomposition Theorem for Maximum Weight Bipartite Matchings
Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1
Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N and W be the node count, the largest edge weight and the total weight of…