A.M. TURING CENTENARY CELEBRATION WEBCAST
  • go to John Backus 's profile page
  • go to A J Milner 's profile page
  • go to Pat Hanrahan's profile page
  • go to Richard W. Hamming's profile page
  • go to Dennis M. Ritchie 's profile page
  • go to Alan Kay's profile page
  • go to Andrew C Yao's profile page
  • go to Kristen Nygaard 's profile page
  • go to Butler W Lampson's profile page
  • go to Prof. Martin Hellman's profile page
  • go to Alfred V Aho's profile page
  • go to Dr. Jack Dongarra's profile page
  • go to Adi Shamir's profile page
  • go to Geoffrey E Hinton's profile page
  • go to Shafi Goldwasser 's profile page
  • go to Juris Hartmanis's profile page
  • go to Peter Naur's profile page
  • go to Maurice V. Wilkes's profile page
  • go to Niklaus E. Wirth's profile page
  • go to Frederick Brooks's profile page
  • go to John L Hennessy's profile page
  • go to John McCarthy's profile page
  • go to J. H. Wilkinson 's profile page
  • go to Ivan Sutherland's profile page
A.M. TURING AWARD WINNERS BY...
Richard Karp

Richard ("Dick") Manning Karp DL Author Profile link

United States – 1985
Short Annotated Bibliography
  1. M. Held and R. M. Karp, "The traveling-salesman problem and minimum spanning trees," Operations Research, vol. 18, no. 6, pp. 1138-1162, Nov. 1970.  This paper explores new approaches to the symmetric traveling-salesman problem in which 1-trees, which are a slight variant of spanning trees, play an essential role.
  2. J. Edmonds and R. M. Karp, "Theoretical improvements in algorithmic efficiency for network flow problems," Journal of the ACM, vol. 19, no. 2, pp. 248-264, April 1972.  This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem and the general minimum-cost flow problem.
  3. R. M. Karp, "Reducibility among combinatorial problems," in Complexity of Computer Computations: Proceedings of a Symposium on the Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., The IBM Research Symposia Series, New York, NY: Plenum Press, 1972, pp. 85-103.  This is the classic paper where the framework is established for proving problems NP-complete. The paper also establishes that twenty-one specific combinatorial problems are NP-complete.
  4. J. E. Hopcroft and R. M. Karp, "An n5/2 algorithm for maximum matchings in bipartite graphs," SIAM Journal of Computing, Vol. 2, Num. 4, pp. 225-231, Dec. 1973.  The paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to (m + n)/sqrt(n).
  5. R. M. Karp, "Turing Award Lecture: Combinatorics, complexity and randomness," Communications of the ACM, Vol. 29, Num. 2, pp. 98-109, Feb. 1986. Karp presents his perspective on the development of the field that has come to be called theoretical computer science.
  6. R. M. Karp and M. O. Rabin, "Efficient randomized pattern-matching algorithms," IBM J. Research and Development, Vol. 31, NUM. 2, pp. 249-260, March 1987.  Randomized algorithms are developed to solve the string-matching problem and some generalizations. They are conceptually simple and easy to implement. The method readily generalizes to higher-dimensional pattern-matching problems.
  7. D. E. Culler, R. M. Karp, D. A. Patterson, A. Sahay, K. E. Schauser, E. E. Santos, R. Subramonian, and T. von Eicken, "LogP: Towards a realistic model of parallel computation," in Proceedings of the. 4th ACM SIGPLAN Symposium. on Principles and Practice of Parallel Programming, New York, NY: ACM Press, 1993, pp. 1-12.  This paper offers a new parallel machine model, called LogP, that reflects the critical technology trends underlying parallel computers. It is intended to serve as a basis for developing fast portable parallel algorithms and to offer guidelines to machine designers.
  8. A. Condon and R. M. Karp, "Algorithms for graph partitioning on the planted partition model," in Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques: Proceedings RANDOM-APPROX '99, D. Hochbaum, K. Jansen, J. D. P. Rolim, and A. Sinclair, Eds., Lecture Notes in Computer Science, Vol. 1671, Berlin, Germany: Springer-Verlag, 1999, pp. 221-232.  The NP-hard graph bisection problem is to partition the nodes of an undirected graph into two equal-sized groups so as to minimize the number of edges that cross the partition. A simple, linear-time algorithm for the problem and extensions of it are analyzed on a random graph model.
  9. E. P. Xing, M. Jordan, and R. M. Karp, "Feature selection for high-dimensional genomic microarray data," in Proceedings of the 18th International Conference on Machine Learning (ICML '01), C. E. Brodley and A. P. Danyluk, Eds., San Francisco, CA, Morgan Kaufmann Publishers Inc., 2001, pp. 601-608.  This paper reports on the successful application of feature selection methods to a classification problem in molecular biology involving only 72 data points in a 7130 dimensional space.
  10. E. Eskin, E. Halperin, and R. M. Karp, "Efficient reconstruction of haplotype structure via perfect phylogeny," Journal of Bioinformatics and Computational Biology, Vol. 1, Num. 1, pp. 1-20, April 2003.  This paper presents a simple and efficient polynomial-time algorithm for inferring haplotypes from the genotypes of a set of individuals assuming a perfect phylogeny. The algorithm is extended to handle constraints that apply when genotypes are available from both parents and child.
  11. R. Sharan, S. Suthram, R. M. Kelley, T. Kuhn, S. McCuine, P. Uetz, T. Sittler, R. M. Karp, and T. Ideker, "Conserved patterns of protein interaction in multiple species," Proceedings of the National Academy of Sciences of the United States of America, Vol. 102, Num. 6, pp. 1974-1979, Feb. 2005.  Multiple comparisons were performed on protein-protein interaction networks of three organisms, revealing 71 network regions that were conserved across all three species. This provides statistically significant support for 4,645 previously undescribed protein functions and 2,609 previously undescribed protein interactions. Many of them would not have been identified from sequence similarity alone, demonstrating that network comparisons provide essential biological information beyond what is gleaned from the genome.
  12. Sharon Bruckner, Falk Hüffner, Richard M. Karp, Ron Shamir and Roded Sharan "Topology-Free Querying of Protein Interaction Networks”, Lecture Notes in Computer Science, 2009, Volume 5541/2009, pp. 74-89  This paper investigates the problem of identifying subsections of proteins from two or more different sources.
  13. R.M Karp, “Heuristic Algorithms in Computational Molecular Biology”, Journal of Computer and System Sciences, Vol. 77, 2011, pp. 122-128.  This paper develops a framework for designing and validating heuristic algorithms for NP-hard problems arising in computational biology and other application areas.