An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings

DOI10.1006/jagm.2001.1163zbMath0982.05095arXivcs/0101010OpenAlexW1967732276WikidataQ58063049 ScholiaQ58063049MaRDI QIDQ2746434

Wing-Kin Sung, Hing-Fung Ting, Tak-Wah Lam, Ming-Yang Kao

Publication date: 8 April 2002

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0101010

zbMATH Keywords

labeled treesevolutionary treesmaximum weight bipartite matchings

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

An \(O(n\log n)\)-time algorithm for the maximum constrained agreement subtree problem for binary trees ⋮ Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species ⋮ Unranked second-order anti-unification ⋮ Improved algorithms for maximum agreement and compatible supertrees ⋮ Tree edit distance and maximum agreement subtree ⋮ Comparing and aggregating partially resolved trees ⋮ Largest Weight Common Subtree Embeddings with Distance Penalties ⋮ Maximum agreement and compatible supertrees ⋮ From constrained to unconstrained maximum agreement subtree in linear time ⋮ Computing the maximum agreement of phylogenetic networks ⋮ An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation ⋮ Faster Algorithms for Semi-Matching Problems ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems

This page was built for publication: An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings