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

Research Output 1988 2017

1993
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
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
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
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
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
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