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

Research Output 1988 2017

1988
12 Citations (Scopus)

All graphs have cycle separators and planar directed depth-first search is in DNC

Kao, M. Y., Jan 1 1988, VLSI Algorithms and Architectures - 3rd Aegean Workshop on Computing, AWOC 1988, Proceedings. Reif, J. H. (ed.). Springer Verlag, p. 53-63 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 319 LNCS).

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

Depth-first Search
Separator
Separators
Directed graphs
Cycle
1989
7 Citations (Scopus)

Local reorientation, global order, and planar topology

Kao, M. Y. & Shannon, G. E., Dec 1 1989, Proc Twenty First Annu ACM Symp Theory Comput. Publ by ACM, p. 286-296 11 p.

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

Topology
Data storage equipment
18 Citations (Scopus)

Parallel depth-first search in general directed graphs

Aggarwal, A., Anderson, R. J. & Kao, M. Y., Dec 1 1989, Proc Twenty First Annu ACM Symp Theory Comput. Publ by ACM, p. 297-308 12 p.

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

Directed graphs
Separators
1990
30 Citations (Scopus)

Parallel depth-first search in general directed graphs

Aggarwal, A., Anderson, R. J. & Kao, M. Y., Jan 1 1990, In : SIAM Journal on Computing. 19, 2, p. 397-409 13 p.

Research output: Contribution to journalArticle

Depth-first Search
Directed graphs
Separators
Directed Graph
Separator
11 Citations (Scopus)

Towards overcoming the transitive-closure bottleneck. Efficient parallel algorithms for planar digraphs

Kao, M. Y. & Klein, P. N., Jan 1 1990, Proc 22nd Annu ACM Symp Theory Comput. Publ by ACM, p. 181-192 12 p. (Proc 22nd Annu ACM Symp Theory Comput).

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

Parallel algorithms
Decomposition
1991
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
1992

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

O(n log log n)-work parallel algorithms for straight-line grid embeddings of planar graphs

Fuerer, M., He, X., Kao, M. Y. & Raghavachari, B., Dec 1 1992, 4th Annual ACM Symposium on Parallel Algorithms and Architectures. Publ by ACM, p. 410-419 10 p.

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

Parallel algorithms
Joining
Data storage equipment
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
3 Citations (Scopus)

Parallel construction of canonical ordering and convex drawing of triconnected planar graphs

He, X. & Kao, M. Y., Jan 1 1993, Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings. Chin, F. Y. L., Raghavan, P., Balasubramanian, N. V. & Ng, K. W. (eds.). Springer Verlag, p. 303-312 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 762 LNCS).

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

Planar graph
Drawing
45 Citations (Scopus)

Scan-first search and sparse certificates. An improved parallel algorithm for k-vertex connectivity

Cheriyan, J., Kao, M. Y. & Thurimella, R., Feb 1 1993, In : SIAM Journal on Computing. 22, 1, p. 154-174 21 p.

Research output: Contribution to journalArticle

Vertex Connectivity
Certificate
Parallel algorithms
Parallel Algorithms
Undirected Graph
40 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., Jan 1 1993, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Publ by ACM, p. 441-447 7 p.

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

Cost functions
Computer science
Costs
Robotics
12 Citations (Scopus)

Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

Kao, M. Y. & Klein, P. N., Jan 1 1993, In : Journal of Computer and System Sciences. 47, 3, p. 459-500 42 p.

Research output: Contribution to journalArticle

Transitive Closure
Reachability
Parallel algorithms
Digraph
Parallel Algorithms
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
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
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
74 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
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
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