Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees

Simple item page
dc.creatorKao, Ming-Yang
dc.creatorLam, Tak-Wah
dc.creatorSung, Wing-Kin
dc.creatorTing, Hing-Fung
dc.date2001-01-26
dc.date2001-01-27
dc.date.accessioned2026-07-07T03:16:54Z
dc.date.available2026-07-07T03:16:54Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/cs/0101031
dc.identifierhttp://arxiv.org/abs/cs/0101031
dc.identifierSIAM Journal on Computing, 30(2):602--624, 2000
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30526
dc.subjectComputational Engineering, Finance, and Science
dc.subjectData Structures and Algorithms
dc.subjectF.2.2; J.3
dc.titleCavity Matchings, Label Compressions, and Unrooted Evolutionary Trees
dc.typetext

Files

Collections

arXiv