康奈尔大学计算机科学系工程与应用数学方向IBM冠名教授（讲座教授组首席教授）

IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University

美国科学院院士、美国工程院院士、中国科学院外籍院士

The Analysis and Modeling of Large Linked Networks (NSF) Information Forensics (AFOSR)

• An approach to a unified theory of automata. BSTJ, Vol. 46:8, October 1967, 1793-1829 (with J. D. Ullman).

• On the equivalence and containment problems for context-free languages. Mathematical Systems Theory, Vol. 3:1, June 1969, 119-124.

• An n log n algorithm for minimizing states in a finite automaton. Theory of Machines and Computations, 189-196, ed. by Z. Kohavi and A. Paz, Academic Press, New York, 1971.

• Efficient algorithms for graph manipulation. Commun. ACM, Vol. 16:6, June 1973, 372-378 (with R. Tarjan).

• Dividing a graph into triconnected components. SIAM J. Computing, Vol. 2:3, September 1973, 135-158 (with R. Tarjan).

• An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Computing, Vol. 2:4, December 1973, 225-231 (with R. Karp).

• Linear time algorithm for isomorphism of planar graphs. Proceedings of 6th Annual ACM Symp. on Theory of Computing, Seattle, Washington (April 30-May 2, 1974) (with J. K. Wong).

• Efficient planarity testing. J. ACM, Vol. 21:4, October 1974, 549-468 (with R. Tarjan). 

• On the reachability problem for 5-dimensional vector addition systems. TCS, Vol. 8, 1979, 135-159 (with J. Pansiot). 

• Efficient detection of intersections among spheres. Intl. J. of Robotics Research, Vol. 2:4, 1983, 77-80 (with J. Schwartz and M. Sharir).