49 citations · 49 across the 2 of their papers we have counts for
11 papers · 1 filter
Improved Phylogeny Comparisons: Non-Shared Edges Nearest Neighbor Interchanges, and Subtree Transfers
Wing-Kai Hon, Ming-Yang Kao, Tak-Wah Lam +2
The number of the non-shared edges of two phylogenies is a basic measure of the dissimilarity between the phylogenies. The non-shared edges are also the building block for approxim…
Linear-Time Algorithms for Computing Maximum-Density Sequence Segments with Bioinformatics Applications
Michael H. Goldwasser, Ming-Yang Kao, Hsueh-I Lu
We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A of pairs (a_i,w_i) for i = 1,..,n and w_i>0, a segment A(i,j) is a consecuti…
Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
Tsan-sheng Hsu, Ming-Yang Kao
A graph is componentwise biconnected if every connected component either is an isolated vertex or is biconnected. We present a linear-time algorithm for the problem of adding the s…
Common-Face Embeddings of Planar Graphs
Zhi-Zhong Chen, Xin He, Ming-Yang Kao
Given a planar graph G and a sequence C_1,...,C_q, where each C_i is a family of vertex subsets of G, we wish to find a plane embedding of G, if any exists, such that for each i in…
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses
Richie Chih-Nan Chuang, Ashim Garg, Xin He +2
Let G be a plane graph of n nodes, m edges, f faces, and no self-loop. G need not be connected or simple (i.e., free of multiple edges). We give three sets of coding schemes for G…
Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings
Xin He, Ming-Yang Kao, Hsueh-I Lu
Let G be an embedded planar undirected graph that has n vertices, m edges, and f faces but has no self-loop or multiple edge. If G is triangulated, we can encode it using {4/3}m-1…