Cavity matchings, label compressions, and unrooted evolutionary trees

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

doi:10.1137/S0097539797332275

Cavity matchings, label compressions, and unrooted evolutionary trees

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

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

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.

Original language	English (US)
Pages (from-to)	602-624
Number of pages	23
Journal	SIAM Journal on Computing
Volume	30
Issue number	2
DOIs	https://doi.org/10.1137/S0097539797332275
State	Published - 2000

Keywords

All-cavity maximum weight matchings
Computational biology
Evolutionary trees
Label compressions
Mixed trees
Unrooted trees

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/S0097539797332275

Cite this

@article{8d51715f04454e468e94559514890856,

title = "Cavity matchings, label compressions, and unrooted evolutionary trees",

abstract = "We present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n1.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.",

keywords = "All-cavity maximum weight matchings, Computational biology, Evolutionary trees, Label compressions, Mixed trees, Unrooted trees",

author = "Kao, {Ming Yang} and Lam, {Tak Wah} and Sung, {Wing Kin} and Ting, {Hing Fung}",

year = "2000",

doi = "10.1137/S0097539797332275",

language = "English (US)",

volume = "30",

pages = "602--624",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Cavity matchings, label compressions, and unrooted evolutionary trees

AU - Kao, Ming Yang

AU - Lam, Tak Wah

AU - Sung, Wing Kin

AU - Ting, Hing Fung

PY - 2000

Y1 - 2000

N2 - We present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n1.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.

AB - We present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n1.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.

KW - All-cavity maximum weight matchings

KW - Computational biology

KW - Evolutionary trees

KW - Label compressions

KW - Mixed trees

KW - Unrooted trees

UR - http://www.scopus.com/inward/record.url?scp=0343337500&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0343337500&partnerID=8YFLogxK

U2 - 10.1137/S0097539797332275

DO - 10.1137/S0097539797332275

M3 - Article

AN - SCOPUS:0343337500

SN - 0097-5397

VL - 30

SP - 602

EP - 624

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -

Cavity matchings, label compressions, and unrooted evolutionary trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this