Pioneer
Richard M. Karp
Also Known As Richard Karp · Richard Manning Karp · Dick Karp · Dick Manning Karp · Dick M. Karp
Theory of Computation
Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley, most notable for his research in the theory of algorithms. He received the 1985 ACM Turing Award, the Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008, and was elected to the National Academy of Engineering in 1992 for contributions to the theory of NP-completeness, efficient combinatorial algorithms, and probabilistic methods in computer science. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
AwardDickson Prize in Science 1 AwardFrederick W. Lanchester Prize 1 AwardFellow of the Society for Industrial and Applied Mathematics 1 Awardhonorary doctorate of Technion 1 Awardhonorary doctorate of the Weizmann Institute of Science 1 AwardJohn von Neumann Theory Prize 1 AwardHarvard Centennial Medal 1 Awardhonorary doctor of ETH Zürich 1 AwardKyoto Prize in Advanced Technology 1 AwardNational Medal of Science 1 AwardBenjamin Franklin Medal 1 AwardBenjamin Franklin Medal 1 Connections
Credited
Source Wikipedia: Edmonds-Karp Algorithm
Source Wikipedia: Held-Karp algorithm
In Field
Source Wikipedia: Richard M. Karp
Invented
Richard Karp co-developed this implementation of the Ford-Fulkerson method for computing maximum flow with Jack Edmonds, published in 1972.
Source Wikipedia: Richard M. Karp
Richard Karp co-developed this dynamic programming algorithm for the traveling salesman problem with Michael Held, published in 1962.
Source Wikipedia: Richard M. Karp
Richard Karp co-developed this algorithm for finding maximum cardinality matchings in bipartite graphs with John Hopcroft, published in 1973.
Source Wikipedia: Richard M. Karp
Richard M. Karp co-developed the string search algorithm with Michael O. Rabin, published in 1987.
In the Other Atlases
Nationality
Also in Geography Atlas: the nationality of this subject.
Sources
1. Wikidata: Richard M. Karp
- Wikidata Q92612, class allow-list match (w-wdresolver-0926)
- Wikidata Q92612 P569 (date of birth)
2. Wikipedia: Richard M. Karp
Wikimedia FoundationLead section
He is most notable for his research in the theory of algorithms, for which he received the 1985 ACM Turing Award, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008. Karp was elected a member of the National Academy of Engineering (1992) for major contributions to the theory and application of NP-completeness, constructing efficient combinatorial algorithms, and applying probabilistic methods in computer science.
Infobox, Born
January 3, 1935
- In Field: Algorithms and Complexity Theory, Lead paragraph
View the Source Wikipedia: Edmonds-Karp Algorithm
Wikimedia FoundationCredited: Edmonds-Karp Algorithm, LeadQuote, Credited: Edmonds-Karp Algorithm, Lead
The algorithm was first published by Yefim Dinitz in 1970, and independently published by Jack Edmonds and Richard Karp in 1972.
Wikipedia: Held-Karp algorithm
Credited: Held-Karp Algorithm, LeadQuote, Credited: Held-Karp Algorithm, Lead
The Held-Karp algorithm, also called the Bellman-Held-Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman and by Held and Karp to solve the traveling salesman problem (TSP), in which the input is a distance matrix between a set of cities, and the goal is to find a minimum-length tour that visits each city exactly once before returning to the starting point.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.