If you made any changes in Pure, your changes will be visible here soon.

Research Output 1988 2017

Article
1 Citation (Scopus)

A combinatorial toolbox for protein sequence design and landscape analysis in the grand canonical model

Aspnes, J., Hartling, J., Kao, M-Y., Kim, J. & Shah, G., Dec 1 2002, In : Journal of Computational Biology. 9, 5, p. 721-741 21 p.

Research output: Contribution to journalArticle

Canonical Model
Protein Sequence
Proteins
Network Flow
Protein
38 Citations (Scopus)

A decomposition theorem for maximum weight bipartite matchings

Kao, M. Y., Lam, T. W., Sung, W. K. & Ting, H. F., Jan 1 2001, In : SIAM Journal on Computing. 31, 1, p. 18-26 9 p.

Research output: Contribution to journalArticle

Bipartite Matching
Decomposition Theorem
Decomposition
Computing
Vertex of a graph
187 Citations (Scopus)

A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry

Chen, T., Tepel, M., Rush, J., Church, G. M. & Kao, M. Y., Jan 1 2001, In : Journal of Computational Biology. 8, 3, p. 325-337 13 p.

Research output: Contribution to journalArticle

Mass Spectrometry
Tandem Mass Spectrometry
Dynamic programming
Peptides
Sequencing
37 Citations (Scopus)

A fast general methodology for information-theoretically optimal encodings of graphs

He, X., Kao, M. Y. & Lu, H. I., Jan 1 2000, In : SIAM Journal on Computing. 30, 3, p. 838-846 9 p.

Research output: Contribution to journalArticle

Labels
Encoding
Methodology
Triangulation
Graph in graph theory
2 Citations (Scopus)

A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis

Johnsen, A., Kao, M-Y. & Seki, S., Feb 1 2017, In : Journal of Combinatorial Optimization. 33, 2, p. 496-529 34 p.

Research output: Contribution to journalArticle

NP-hardness
Self-assembly
Tile
Self assembly
Hardness
9 Citations (Scopus)

An approximation algorithm for a bottleneck traveling salesman problem

Kao, M-Y. & Sanghi, M., Sep 1 2009, In : Journal of Discrete Algorithms. 7, 3, p. 315-326 12 p.

Research output: Contribution to journalArticle

Traveling salesman problem
Approximation algorithms
Travelling salesman problems
Approximation Algorithms
Operations research
43 Citations (Scopus)

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

Kao, M. Y., Lam, T. W., Sung, W. K. & Ting, H. F., Jan 1 2001, In : Journal of Algorithms. 40, 2, p. 212-233 22 p.

Research output: Contribution to journalArticle

Bipartite Matching
Labeled Trees
Matching Problem
Leaves
Evolutionary Tree
4 Citations (Scopus)

An optimal parallel algorithm for planar cycle separators

Kao, M. Y., Teng, S. H. & Toyama, K., Nov 1 1995, In : Algorithmica. 14, 5, p. 398-408 11 p.

Research output: Contribution to journalArticle

Depth-first Search
Separator
Search Trees
Separators
Optimal Algorithm
8 Citations (Scopus)

A Unifying Augmentation Algorithm for Two-Edge Connectivity and Biconnectivity

Hsu, T. S. & Kao, M. Y., Jan 1 1998, In : Journal of Combinatorial Optimization. 2, 3, p. 237-256 20 p.

Research output: Contribution to journalArticle

Edge-connectivity
Augmentation
Edge-disjoint Paths
Disjoint Paths
Graph in graph theory
2 Citations (Scopus)

Average case analysis for tree labelling schemes

Kao, M-Y., Li, X. Y. & Wang, W., Jun 9 2007, In : Theoretical Computer Science. 378, 3, p. 271-291 21 p.

Research output: Contribution to journalArticle

Average-case Analysis
Labeling Scheme
Labeling
Labels
Separator
9 Citations (Scopus)

Cavity matchings, label compressions, and unrooted evolutionary trees

Kao, M. Y., Lam, T. W., Sung, W. K. & Ting, H. F., Jan 1 2000, In : SIAM Journal on Computing. 30, 2, p. 602-624 23 p.

Research output: Contribution to journalArticle

Evolutionary Tree
Labels
Cavity
Compression
Backbone
1 Citation (Scopus)

Common-face embeddings of planar graphs

Chen, Z. Z., He, X. & Kao, M-Y., Feb 1 2003, In : SIAM Journal on Computing. 32, 2, p. 408-434 27 p.

Research output: Contribution to journalArticle

Planar graph
Computational complexity
Face
Recovery
Processing
103 Citations (Scopus)

Complexities for generalized models of self-assembly

Aggarwal, G., Cheng, Q. I., Goldwasser, M. H., Kao, M-Y., De Espanes, P. M. & Schweller, R. T., Dec 1 2005, In : SIAM Journal on Computing. 34, 6, p. 1493-1515 23 p.

Research output: Contribution to journalArticle

Self-assembly
Tile
Self assembly
Lower bound
Glues
36 Citations (Scopus)

Data security equals graph connectivity

Kao, M. Y., Jan 1 1996, In : SIAM Journal on Discrete Mathematics. 9, 1, p. 87-100 14 p.

Research output: Contribution to journalArticle

Graph Connectivity
Data Security
Table
NP-completeness
Cell

Designing proxies for stock market indices is computationally hard

Kao, M-Y. & Tate, S. R., 2001, In : Quantitative Finance. 1, p. 361-371

Research output: Contribution to journalArticle

Stock market index
Market index
Relative prices
Margin
Stock market
40 Citations (Scopus)

Design optimization methods for genomic DNA tiling arrays

Bertone, P., Trifonov, V., Rozowsky, J. S., Schubert, F., Emanuelsson, O., Karro, J., Kao, M-Y., Snyder, M. & Gerstein, M., Feb 1 2006, In : Genome Research. 16, 2, p. 271-281 11 p.

Research output: Contribution to journalArticle

Oligonucleotide Array Sequence Analysis
Genome
DNA Fragmentation
Oligonucleotides
DNA
1 Citation (Scopus)

Deterministic polynomial-time algorithms for designing short DNA words

Kao, M-Y., Leung, H. C. M., Sun, H. & Zhang, Y., Jul 8 2013, In : Theoretical Computer Science. 494, p. 144-160 17 p.

Research output: Contribution to journalArticle

Deterministic Algorithm
Polynomial-time Algorithm
DNA
Polynomials
Randomized Algorithms
1 Citation (Scopus)

Discovering almost any hidden motif from multiple sequences

Fu, B., Kao, M-Y. & Wang, L., Mar 1 2011, In : ACM Transactions on Algorithms. 7, 2, 26.

Research output: Contribution to journalArticle

Motif Discovery
Probabilistic Model
Efficient Algorithms
Strings
Subset
3 Citations (Scopus)

Efficient broadcast on hypercubes with wormhole and e-cube routings

Ho, C. T. & Kao, M. Y., Jan 1 1995, In : Parallel Processing Letters. 5, 2, p. 213-222 10 p.

Research output: Contribution to journalArticle

Wormhole
Routing algorithms
Broadcasting
Hypercube
Broadcast
3 Citations (Scopus)

Efficient Detection and Protection of Information in Cross Tabulated Tables I: Linear Invariant Test

Kao, M-Y. & Gusfield, D., Aug 1993, In : SIAM Journal on Discrete Mathematics. 6, p. 460-476

Research output: Contribution to journalArticle

Tables
Table
Invariant
Cell
Linear Combination
5 Citations (Scopus)
Tables
Decomposition
Table
Invariant
Correspondence

Efficient submesh permutations in wormhole-routed meshes

Ho, C. T. & Kao, M. Y., Jan 1 1998, In : Information Sciences. 107, 1-4, p. 1-13 13 p.

Research output: Contribution to journalArticle

Wormhole
Congestion
Permutation
Routing
Mesh
10 Citations (Scopus)

Fast optimal genome tiling with applications to microarray design and homology search

Herman, P., Bertone, P., Dasgupta, B., Gerstein, M., Kao, M-Y. & Snyder, M., Sep 28 2004, In : Journal of Computational Biology. 11, 4, p. 766-785 20 p.

Research output: Contribution to journalArticle

Microarrays
Tile
Tiling
Microarray
Homology
5 Citations (Scopus)

Fast universalisation of investment strategies

Akcoglu, K., Drineas, P. & Kao, M-Y., Apr 15 2005, In : SIAM Journal on Computing. 34, 1, p. 1-22 22 p.

Research output: Contribution to journalArticle

Approximation algorithms
Beaches
Computer science
Trading Strategies
Universal Cover
17 Citations (Scopus)

General techniques for comparing unrooted evolutionary trees

Kao, M. Y., Lam, T. W., Przytycka, T. M., Sung, W. K. & Ting, H. F., Jan 1 1997, In : Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 54-65 12 p.

Research output: Contribution to journalArticle

Dynamic programming
Labels

Gridding and discretization for divergence form (semiconductor-like) PDEs

Kao, M. Y., Rose, D. J. & Shao, H., Jan 1 1998, In : VLSI Design. 6, 1-4, p. 111-115 5 p.

Research output: Contribution to journalArticle

Partial differential equations
Conservation
Semiconductor materials
Finite element method
Convection
8 Citations (Scopus)

Linear-processor NC algorithms for planar directed graphs I: Strongly connected components

Kao, M. Y., Jan 1 1993, In : SIAM Journal on Computing. 22, 3, p. 431-459 29 p.

Research output: Contribution to journalArticle

Directed graphs
Connected Components
Directed Graph
Planar graph
Random Access
2 Citations (Scopus)

Linear-time accurate lattice algorithms for tail conditional expectation

Chen, B., Hsu, W. W. Y., Ho, J. M. & Kao, M-Y., Jan 1 2014, In : Algorithmic Finance. 3, 1-2, p. 87-140 54 p.

Research output: Contribution to journalArticle

Conditional Expectation
Linear Time
Tail
Extrapolation
Fractional Step
34 Citations (Scopus)

Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications

Goldwasser, M. H., Kao, M-Y. & Lu, H. I., Mar 1 2005, In : Journal of Computer and System Sciences. 70, 2, p. 128-144 17 p.

Research output: Contribution to journalArticle

Bioinformatics
Linear-time Algorithm
Computing
Sequence Analysis
Subsequence
5 Citations (Scopus)

Linear-time approximation algorithms for computing numerical summation with provably small errors

Kao, M. Y. & Wang, J., Jan 1 2000, In : SIAM Journal on Computing. 29, 5, p. 1568-1576 9 p.

Research output: Contribution to journalArticle

Worst Case Error
Approximation algorithms
Linear-time Algorithm
Summation
Approximation Algorithms
1 Citation (Scopus)

Linear-time haplotype inference on pedigrees without recombinations and mating loops

Chan, M. Y., Chan, W. T., Chin, F. Y. L., Fung, S. P. Y. & Kao, M-Y., Jun 1 2009, In : SIAM Journal on Computing. 38, 6, p. 2179-2197 19 p.

Research output: Contribution to journalArticle

Pedigree
Haplotype
Linear equations
Recombination
Linear Time
8 Citations (Scopus)

Linear-time optimal augmentation for componentwise bipartite-completeness of graphs

Kao, M. Y., Apr 14 1995, In : Information Processing Letters. 54, 1, p. 59-63 5 p.

Research output: Contribution to journalArticle

Design of Algorithms
Analysis of Algorithms
Augmentation
Combinatorial Problems
Linear Time
39 Citations (Scopus)

Linear-time succinct encodings of planar graphs via canonical orderings

He, X., Kao, M. Y. & Lu, H. I., Jan 1 1999, In : SIAM Journal on Discrete Mathematics. 12, 3, p. 317-325 9 p.

Research output: Contribution to journalArticle

Planar graph
Linear Time
Encoding
Exponential time
Undirected Graph

Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees

Kao, M. Y. & Wang, J., Aug 2 2001, In : Theoretical Computer Science. 262, 1-2, p. 101-115 15 p.

Research output: Contribution to journalArticle

Rounding error
Prefix
Worst Case Error
Floating point
Subsequence
2 Citations (Scopus)

Non-shared edges and nearest neighbor interchanges revisited

Hon, W. K., Kao, M-Y., Lam, T. W., Sung, W. K. & Yiu, S. M., Aug 16 2004, In : Information Processing Letters. 91, 3, p. 129-134 6 p.

Research output: Contribution to journalArticle

Interchanges
Nearest Neighbor
Phylogeny
Approximation algorithms
Dissimilarity

Not all planar diagraphs have small cycle separators

Kao, M. Y. & Wan, F., Nov 19 1992, In : Information Processing Letters. 44, 2, p. 79-83 5 p.

Research output: Contribution to journalArticle

Separator
Separators
Directed graphs
Cycle
Directed Graph
6 Citations (Scopus)

On approximating four covering and packing problems

Ashley, M., Berger-Wolf, T., Berman, P., Chaovalitwongse, W., DasGupta, B. & Kao, M-Y., Aug 1 2009, In : Journal of Computer and System Sciences. 75, 5, p. 287-302 16 p.

Research output: Contribution to journalArticle

Covering Problem
Packing Problem
Inapproximability
Approximability
Profitability
9 Citations (Scopus)

On constructing an optimal consensus clustering from multiple clusterings

Berman, P., DasGupta, B., Kao, M-Y. & Wang, J., Nov 15 2007, In : Information Processing Letters. 104, 4, p. 137-145 9 p.

Research output: Contribution to journalArticle

Clustering
Partition
Approximation algorithms
Similarity Measure
Data mining
8 Citations (Scopus)

On-line difference maximization

Kao, M. Y. & Tate, S. R., Jan 1 1999, In : SIAM Journal on Discrete Mathematics. 12, 1, p. 78-90 13 p.

Research output: Contribution to journalArticle

Optimal Algorithm
Scenarios
Line
Stochastic Games
Maximise
14 Citations (Scopus)

Online matching with blocked input

Kao, M. Y. & Tate, S. R., May 17 1991, In : Information Processing Letters. 38, 3, p. 113-116 4 p.

Research output: Contribution to journalArticle

Matching Problem
Upper bound
Bipartite Matching
Term
Graph in graph theory
4 Citations (Scopus)

Optimal augmentation for bipartite componentwise biconnectivity in linear time

Hsu, T. S. & Kao, M-Y., Dec 1 2005, In : SIAM Journal on Discrete Mathematics. 19, 2, p. 345-362 18 p.

Research output: Contribution to journalArticle

Augmentation
Linear-time Algorithm
Connected Components
Bipartite Graph
Tables
5 Citations (Scopus)

Optimal bidding algorithms against cheating in multiple-object auctions

Kao, M. Y., Qi, J. & Tan, L., Dec 1 1999, In : SIAM Journal on Computing. 28, 3, p. 955-969 15 p.

Research output: Contribution to journalArticle

Bidding
Auctions
Closed-form Solution
Object
Multivariate Distribution
36 Citations (Scopus)

Optimal Broadcast in All-Port Wormhole-Routed Hypercubes

Ho, C. T. & Kao, M. Y., Jan 1 1995, In : IEEE Transactions on Parallel and Distributed Systems. 6, 2, p. 200-204 5 p.

Research output: Contribution to journalArticle

Routing algorithms
Communication
26 Citations (Scopus)

Optimal buy-and-hold strategies for financial markets with bounded daily returns

Chen, G. H., Kao, M. Y., Lyuu, Y. D. & Wong, H. K., Jan 1 2001, In : SIAM Journal on Computing. 31, 2, p. 447-459 13 p.

Research output: Contribution to journalArticle

Financial Markets
Investment Analysis
Game
Competitive Ratio
Online Algorithms
7 Citations (Scopus)

Optimal buy-and-hold strategies for financial markets with bounded daily returns

Chen, G. H., Kao, M. Y., Lyuu, Y. D. & Wong, H. K., Jan 1 1999, In : Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 119-128 10 p.

Research output: Contribution to journalArticle

Game theory
Financial markets
32 Citations (Scopus)

Optimal Constructions of Hybrid Algorithms

Kao, M. Y., Ma, Y., Sipser, M. & Yin, Y., Jan 1 1998, In : Journal of Algorithms. 29, 1, p. 142-164 23 p.

Research output: Contribution to journalArticle

Hybrid Algorithm
Randomized Algorithms
Competitive Ratio
Deterministic Algorithm
Resolve
22 Citations (Scopus)

Optimal On-Line Scheduling of Parallel Jobs with Dependencies

Feldmann, A., Kao, M. Y., Sgall, J. & Teng, S. H., Jan 1 1998, In : Journal of Combinatorial Optimization. 1, 4, p. 393-411 19 p.

Research output: Contribution to journalArticle

Optimal Scheduling
Scheduling
Mesh
Virtualization
Competitive Ratio

Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs

Kao, M-Y., Fürer, M., He, X. & Raghavachari, B., 1994, In : SIAM Journal on Discrete Mathematics. 7, p. 632-646

Research output: Contribution to journalArticle

Optimal Algorithm
Straight Line
Planar graph
Parallel Algorithms
Grid
1 Citation (Scopus)

Optimal search for parameters in Monte Carlo simulation for derivative pricing

Wang, C. J. & Kao, M-Y., Mar 1 2016, In : European Journal of Operational Research. 249, 2, p. 683-690 8 p.

Research output: Contribution to journalArticle

Pricing
Monte Carlo Simulation
Online Algorithms
Derivatives
Derivative

Outstanding principal as prepayment value: A closed-form formula for mortgage pricing

Tsai, Y. C., Lei, C. L., Ho, J. M., Kao, M-Y. & Liao, S. L., May 1 2015, In : Journal of Information Science and Engineering. 31, 3, p. 925-942 18 p.

Research output: Contribution to journalArticle

pricing
Risk management
Costs
Values
financial market