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

Research Output 1988 2017

1999
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
13 Citations (Scopus)

Nonplanar topological inference and political-map graphs

Chen, Z. Z., He, X. & Kao, M. Y., Jan 1 1999, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Anon (ed.). SIAM, p. 195-204 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Printed circuit boards
Polynomials
Graph in graph theory
Mixed Graphs
Inclusion Relations
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
1 Citation (Scopus)

On the informational asymmetry between upper and lower bounds for ultrametric evolutionary trees

Chen, T. & Kao, M. Y., Jan 1 1999, Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. Nešetřil, J. (ed.). Springer Verlag, p. 248-256 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1643).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Evolutionary Tree
Asymmetry
Upper and Lower Bounds
Testing
Pairwise
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
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
13 Citations (Scopus)

Recovering evolutionary trees through harmonic greedy triplets

Csuros, M. & Kao, M. Y., Jan 1 1999, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Anon (ed.). SIAM, p. 261-270 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Evolutionary Tree
Harmonic
Trees (mathematics)
Topology
Polynomials
1998
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
56 Citations (Scopus)

Compact encodings of planar graphs via canonical orderings and multiple parentheses

Chuang, R. C. N., Garg, A., He, X., Kao, M. Y. & Lu, H. I., Dec 1 1998, Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. p. 118-129 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1443 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Planar graph
Decoding
Encoding
Coding
Adjacency

Computing and combinatorics: 4th annual international conference COCOON’98 Taipei, Taiwan, R.o.C., august 12-14, 1998 proceedings

Hsu, W. L. & Kao, M. Y., Jan 1 1998, Computing and Combinatorics - 4th Annual International Conference COCOON 1998, Proceedings. Springer Verlag, Vol. 1449. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1449).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Taiwan
Combinatorics
Annual
Computing
1 Citation (Scopus)

Efficient minimization of numerical summation errors

Kao, M. Y. & Wang, J., Dec 1 1998, Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. p. 375-386 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1443 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Worst Case Error
Summation
Approximation Algorithms
Floating point
Approximation algorithms

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

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
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
10 Citations (Scopus)

Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs

Kao, M. Y., Occhiogrosso, N. & Teng, S. H., Jan 1 1998, In : Journal of Combinatorial Optimization. 2, 4, p. 351-359 9 p.

Research output: Contribution to journalArticle

Compression
Complement
Graph in graph theory
Adjacency
Optimal Algorithm
24 Citations (Scopus)

Tree contractions and evolutionary trees

Kao, M. Y., Jan 1 1998, In : SIAM Journal on Computing. 27, 6, p. 1592-1616 25 p.

Research output: Contribution to journalArticle

Evolutionary Tree
Contraction
Leaves
Rooted Trees
Maximum Degree
1997
13 Citations (Scopus)

All-cavity maximum matchings

Kao, M. Y., Lam, T. W., Sung, W. K. & Ting, H. F., Jan 1 1997, Algorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings. Leong, H. W., Jain, S. & Imai, H. (eds.). Springer Verlag, p. 364-373 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1350).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Maximum Matching
Cavity
Count
Vertex of a graph
Denote
5 Citations (Scopus)
Tables
Decomposition
Table
Invariant
Correspondence
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
1 Citation (Scopus)

On-line difference maximization

Kao, M. Y. & Tate, S. R., Jan 1 1997, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Anon (ed.). ACM, p. 175-182 8 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Stochastic Games
Optimal Algorithm
Maximise
Distinct
Arbitrary

Optimal bidding algorithms against cheating in multiple-object auctions

Kao, M. Y., Qi, J. & Tan, L., Jan 1 1997, Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings. Springer Verlag, p. 192-201 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1276).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Reducing randomness via irrational numbers

Chen, Z. Z. & Kao, M. Y., Jan 1 1997, In : Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 200-209 10 p.

Research output: Contribution to journalArticle

Polynomials
Testing
Error probability
6 Citations (Scopus)

Security problems for statistical databases with general cell suppressions

Hsu, T. S. & Kao, M. Y., Jan 1 1997, Scientific and Statistical Database Management - Proceedings of the International Working Conference. IEEE, p. 155-164 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Security of data
Cell
Table
Data Security
Invariant
10 Citations (Scopus)

Total protection of analytic-invariant information in cross-tabulated tables

Kao, M. Y., Jan 1 1997, In : SIAM Journal on Computing. 26, 1, p. 231-242 12 p.

Research output: Contribution to journalArticle

Tables
Invariant
Cell
Table
Linear-time Algorithm

Tree contractions and evolutionary trees

Kao, M. Y., Jan 1 1997, Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings. Bongiovanni, G., Bovet, D. P. & Di Battista, G. (eds.). Springer Verlag, p. 299-310 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1203).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Evolutionary Tree
Contraction
Leaves
Rooted Trees
Maximum Degree
1996
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
6 Citations (Scopus)

Optimal augmentation for bipartite componentwise biconnectivity in linear time

Hsu, T. S. & Kao, M. Y., Jan 1 1996, Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. Nagamochi, H., Miyano, S., Asano, T., Igarashi, Y. & Suri, S. (eds.). Springer Verlag, p. 213-222 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1178).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Augmentation
Linear Time
Linear-time Algorithm
Connected Components
Bipartite Graph
75 Citations (Scopus)

Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem

Kao, M. Y., Reif, J. H. & Tate, S. R., Nov 25 1996, In : Information and Computation. 131, 1, p. 63-79 17 p.

Research output: Contribution to journalArticle

Randomized Algorithms
Optimal Algorithm
Unknown
Path
Deterministic Algorithm
1995
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
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
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
75 Citations (Scopus)

Load balancing in the Lp norm

Awerbuch, B., Azar, Y., Grove, E. F., Kao, M. Y., Krishnan, P. & Vitter, J. S., Dec 1 1995, In : Annual Symposium on Foundations of Computer Science - Proceedings. p. 383-391 9 p.

Research output: Contribution to journalConference article

Resource allocation
Servers
2 Citations (Scopus)

Minimal linear invariants

Kao, M. Y., Jan 1 1995, Algorithms, Concurrency and Knowledge - 1995 Asian Computing Science Conference, ACSC 1995, Proceedings. Levy, J-J. & Kanchanasut, K. (eds.). Springer Verlag, p. 23-33 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1023).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Invariant
Table
Correspondence
Cell
Linear-time Algorithm
11 Citations (Scopus)

Online perfect matching and mobile computing

Grove, E. F., Kao, M. Y., Krishnan, P. & Vitter, J. S., Jan 1 1995, Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings. Akl, S. G., Dehne, F., Sack, J-R. & Santoro, N. (eds.). Springer Verlag, p. 194-205 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 955).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Mobile computing
Mobile Computing
Perfect Matching
Customers
Switches
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
5 Citations (Scopus)

Planar strong connectivity helps in parallel depth-first search

Kao, M. Y., Jan 1 1995, In : SIAM Journal on Computing. 24, 1, p. 46-62 17 p.

Research output: Contribution to journalArticle

Strong Connectivity
Depth-first Search
Directed graphs
Directed Graph
Planar graph
4 Citations (Scopus)

Regular edge labelings and drawings of planar graphs

He, X. & Kao, M. Y., Jan 1 1995, Graph Drawing - DIMACS International Workshop, GD 1994, Proceedings. Springer Verlag, p. 96-103 8 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 894).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Edge Labeling
Planar graph
Labeling
Labels
Graph Drawing
1994
4 Citations (Scopus)

Data compression techniques for stock market prediction

Azhar, S., Badros, G. J., Glodjo, A., Kao, M. Y. & Reif, J. H., Jan 1 1994, Proceedings of the Data Compression Conference. Storer, J. A. & Cohn, M. (eds.). Publ by IEEE, p. 72-82 11 p.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Data compression
Correlation theory
Finance
Taxation
Costs

Efficient submesh permutations in wormhole-routed meshes

Ho, C. T. & Kao, M. Y., Dec 1 1994, In : IEEE Symposium on Parallel and Distributed Processing - Proceedings. p. 672-678 7 p.

Research output: Contribution to journalConference article

3 Citations (Scopus)

Optimal broadcast in all-port wormhole-routed hypercubes

Ho, C. T. & Kao, M. Y., Jan 1 1994, In : Proceedings of the International Conference on Parallel Processing. 3, 5727852.

Research output: Contribution to journalConference article

Wormhole
Hypercube
Broadcast
Routing
Routing algorithms
11 Citations (Scopus)

Optimal constructions of hybrid algorithms

Kao, M. Y., Ma, Y., Sipser, M. & Yin, Y., Jan 1 1994, Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. Publ by ACM, p. 372-381 10 p. (Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Hybrid Algorithm
Randomized Algorithms
Competitive Ratio
Deterministic Algorithm
Resolve

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
2 Citations (Scopus)

Simple and efficient graph compression schemes for dense and complement graphs

Kao, M. Y. & Teng, S. H., Jan 1 1994, Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings. Du, D-Z., Du, D-Z. & Zhang, X-S. (eds.). Springer Verlag, p. 451-459 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 834 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Compression
Complement
Graph in graph theory
Adjacency
Optimal Algorithm

Total protection of analytic invariant information in cross tabulated tables

Kao, M. Y., Jan 1 1994, STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Mayr, E. W., Wagner, K. W. & Enjalbert, P. (eds.). Springer Verlag, p. 723-734 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 775 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Tables
Invariant
Cell
Table
Testing
1993
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

Improved parallel depth-first search in undirected planar graphs

Kao, M. Y., Teng, S. H. & Toyama, K., Jan 1 1993, Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Dehne, F., Sack, J-R., Santoro, N. & Whitesides, S. (eds.). Springer Verlag, p. 409-420 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 709 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Depth-first Search
Undirected Graph
Planar graph
Separator
Search Trees
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
33 Citations (Scopus)

Optimal online scheduling of parallel jobs with dependencies

Feldmann, A., Kao, M. Y., Sgall, J. & Teng, S. H., Jun 1 1993, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery, p. 642-651 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129585).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Scheduling
Scheduling algorithms
Communication