Edit Profile (opens in new tab) Karp, Richard Manning Compute Distance To: Compute Author ID: karp.richard-m Published as: Karp, Richard M.; Karp, R. M.; Karp, Richard; Karp, R. Homepage: http://www.cs.berkeley.edu/~karp External Links: MGP · Wikidata · dblp · GND · IdRef Awards: Turing Award (1985) Documents Indexed: 148 Publications since 1961 1 Contribution as Editor · 5 Further Contributions Biographic References: 2 Publications Co-Authors: 135 Co-Authors with 113 Joint Publications 5,277 Co-Co-Authors all top 5 Co-Authors 40 single-authored 7 Luby, Michael G. 7 Miller, Raymond E. 5 Adler, Ilan 5 Held, Michael 5 Ross, Sheldon Mark 5 Wigderson, Avi 4 Adler, Micah 4 Daskalakis, Constantinos 4 Edmonds, Jack R. 4 Kenyon, Claire M. 4 Lipton, Richard J. 4 Papadimitriou, Christos Harilaos 3 Alizadeh, Farid 3 El-Yaniv, Ran 3 Even, Shimon 3 Fiat, Amos 3 Gibbons, Phillip B. 3 Halperin, Eran 3 Hopcroft, John Edward H. 3 Miller, Gary Lee 3 Shamir, Ron 3 Sharan, Roded 3 Soroker, Danny 3 Tarjan, Robert Endre 3 Waarts, Orli 3 Weisser, Deborah K. 3 Zhang, Yanjun 2 Ahn, Hyun-Soo 2 Alon, Noga M. 2 Beame, Paul W. 2 Borodin, Allan B. 2 Byers, John W. 2 Condon, Anne E. 2 Dagum, Paul 2 Dimakis, Alexandros G. 2 Dolev, Danny 2 Guibas, Leonidas John 2 Jiang, Tao 2 Karmarkar, Narendra K. 2 Moreno-Centeno, Erick 2 Mossel, Elchanan 2 Motwani, Rajeev 2 Newberg, Lee Aaron 2 Pearl, Judea 2 Peleg, David 2 Pitassi, Toniann 2 Pratt, Vaughan R. 2 Ramachandran, Vijaya 2 Riesenfeld, Samantha J. 2 Rinnooy Kan, Alexander Hendrik George 2 Rivest, Ronald Linn 2 Saks, Michael E. 2 Shenker, Scott J. 2 Turpin, G. 2 Ullman, Jeffrey David 2 Upfal, Eli 2 Vazirani, Vijay V. 2 Verbin, Elad 2 Wainwright, Martin J. 2 West, Douglas Brent 2 Winograd, Shmuel 2 Zweig, Geoffrey 1 Alt, Helmut 1 Amanatidis, Christos 1 Angluin, Dana 1 Behnezhad, Soheil 1 Blömer, Johannes 1 Bloniarz, Peter A. 1 Blum, Lenore 1 Blum, Manuel 1 Brandt, Sebastian F. 1 Brent, Richard Peirce 1 Brown, Donna J. 1 Cao, Yang 1 Carey, M. R. 1 Carlson, David A. 1 Chandrasekaran, Karthekeyan 1 Chazelle, Bernard 1 Cook, Stephen Arthur 1 Cucker, Felipe 1 Cypher, A. 1 DeMillo, Richard A. 1 Derakhshan, Mahsa 1 Dobkin, David P. 1 Ehrig, Hartmut 1 Elson, Jeremy 1 Even, Guy 1 Fagin, Ronald 1 Feustel, Charles D. 1 Filotti, I. S. 1 Fischer, Manuela 1 Fischer, Michael J. 1 Floyd, Robert W. 1 Floyd, Sally 1 Fowler, Glenn S. 1 Frazer, W. Donald 1 Frederickson, Greg N. 1 Frieze, Alan Michael 1 Gale, David 1 Gat-Viks, Irit ...and 118 more Co-Authors all top 5 Serials 12 SIAM Journal on Computing 9 Algorithmica 7 Journal of the Association for Computing Machinery 6 Random Structures & Algorithms 5 Mathematics of Operations Research 4 Discrete Applied Mathematics 4 Journal of Computer and System Sciences 4 Operations Research 4 Journal of Algorithms 3 Networks 3 SIAM Journal on Applied Mathematics 2 Discrete Mathematics 2 Journal of Applied Probability 2 Kiberneticheskiĭ Sbornik. Novaya Seriya 2 Journal of Complexity 2 SIAM Journal on Discrete Mathematics 2 Journal of Combinatorial Theory 2 Journal of the Society for Industrial & Applied Mathematics 1 Artificial Intelligence 1 IEEE Transactions on Information Theory 1 Information Processing Letters 1 Information and Control 1 Mathematical Programming 1 Theoretical Computer Science 1 Operations Research Letters 1 Combinatorica 1 Journal of Computer Science and Technology 1 Internationale Mathematische Nachrichten 1 Games and Economic Behavior 1 Communications of the ACM 1 L’Enseignement Mathématique. 2e Série 1 IBM Journal of Research and Development 1 Pokroky Matematiky, Fyziky & Astronomie 1 Notices of the American Mathematical Society 1 Theory of Computing Systems 1 Journal of the ACM 1 Communications in Information and Systems 1 Discrete Optimization 1 Management Science. Ser. A, Theory Series 1 IEEE Transactions on Electronic Computers 1 IRE Transactions on Information Theory all top 5 Fields 96 Computer science (68-XX) 46 Operations research, mathematical programming (90-XX) 37 Combinatorics (05-XX) 16 Biology and other natural sciences (92-XX) 14 Information and communication theory, circuits (94-XX) 10 Numerical analysis (65-XX) 10 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 8 Probability theory and stochastic processes (60-XX) 4 General and overarching topics; collections (00-XX) 4 History and biography (01-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 2 Number theory (11-XX) 1 Mathematical logic and foundations (03-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Statistics (62-XX) 1 Statistical mechanics, structure of matter (82-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 127 Publications have been cited 4,702 times in 4,186 Documents Cited by ▼ Year ▼ Reducibility among combinatorial problems. Zbl 0366.68041Karp, R. M. 692 1975 A \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. Zbl 0266.05114Hopcroft, John E.; Karp, Richard M. 408 1973 Theoretical improvements in algorithmic efficiency for network flow problems. Zbl 0318.90024Edmonds, Jack; Karp, Richard M. 324 1972 The traveling-salesman problem and minimum spanning trees. Zbl 0226.90047Held, Michael; Karp, Richard M. 233 1970 A dynamic programming approach to sequencing problems. Zbl 0106.14103Held, Michael; Karp, Richard M. 232 1962 The traveling-salesman problem and minimum spanning trees. II. Zbl 0232.90038Held, Michael; Karp, Richard M. 198 1971 Parallel algorithms for shared-memory machines. Zbl 0900.68267Karp, Richard M.; Ramachandran, Vijaya 179 1990 Parallel program schemata. Zbl 0198.32603Karp, Richard M.; Miller, Raymond E. 174 1969 A characterization of the minimum cycle mean in a digraph. Zbl 0386.05032Karp, Richard M. 173 1978 Reducibility among combinatorial problems. Zbl 1467.68065Karp, Richard M. 144 1972 On the computational complexity of combinatorial problems. Zbl 0324.05003Karp, R. M. 128 1975 Efficient randomized pattern-matching algorithms. Zbl 0653.68054Karp, Richard M.; Rabin, Michael O. 105 1987 Probabilistic analysis of partitioning algorithms for the traveling- salesman problem in the plane. Zbl 0391.90091Karp, Richard M. 70 1977 On nonterminating stochastic games. Zbl 0136.14303Hoffman, A. J.; Karp, R. M. 68 1966 Turing machines that take advice. Zbl 0529.68025Karp, Richard M.; Lipton, Richard J. 59 1982 Competitive paging algorithms. Zbl 0753.68018Fiat, Amos; Karp, Richard M.; Luby, Michael; McGeoch, Lyle A.; Sleator, Daniel D.; Young, Neal E. 59 1991 Constructing a perfect matching is in random NC. Zbl 0646.05051Karp, R. M.; Upfal, E.; Wigderson, A. 55 1986 On the power of randomization in on-line algorithms. Zbl 0784.68038Ben-David, S.; Borodin, A.; Karp, R.; Tardos, G.; Wigderson, A. 54 1994 The transitive closure of a random digraph. Zbl 0712.68076Karp, Richard M. 51 1990 A patching algorithm for the nonsymmetric traveling-salesman problem. Zbl 0427.90064Karp, Richard M. 49 1979 The organization of computations for uniform recurrence equations. Zbl 0171.38305Karp, Richard M.; Miller, Raymond E.; Winograd, Shmuel 49 1967 Monte-Carlo approximation algorithms for enumeration problems. Zbl 0678.65001Karp, Richard M.; Luby, Michael; Madras, Neal 46 1989 A fast parallel algorithm for the maximal independent set problem. Zbl 0633.68026Karp, Richard M.; Wigderson, Avi 46 1985 Finite-state processes and dynamic programming. Zbl 0155.28701Karp, R. M.; Held, M. 42 1967 A graph-theoretic game and its application to the \(k\)-server problem. Zbl 0818.90147Alon, Noga; Karp, Richard M.; Peleg, David; West, Douglas 41 1995 Application-level multicast using content-addressable networks. Zbl 1060.68544Ratnasamy, Sylvia; Handley, Mark; Karp, Richard; Shenker, Scott 35 2001 Monte-Carlo algorithms for the planar multiterminal network reliability problem. Zbl 0596.90033Karp, Richard M.; Luby, Michael 35 1985 Reducibility among combinatorial problems. Zbl 1187.90014Karp, Richard M. 34 2010 Optimal search and one-way trading online algorithms. Zbl 0984.68043El-Yaniv, R.; Fiat, A.; Karp, R. M.; Turpin, G. 33 2001 Mapping the genome, some combinatorial problems arising in molecular biology. Zbl 1310.92022Karp, Richard M. 33 1993 Dynamic programming meets the principle of inclusion and exclusion. Zbl 0486.90083Karp, Richard M. 32 1982 Probabilistic analysis of heuristics. Zbl 0582.90100Karp, R. M.; Steele, J. M. 30 1985 Parametric shortest path algorithms with an application to cyclic staffing. Zbl 0453.68032Karp, Richard M.; Orlin, James B. 29 1981 Algorithms for graph partitioning on the planted partition model. Zbl 0972.68129Condon, Anne; Karp, Richard M. 28 2001 On linear characterizations of combinatorial optimization problems. Zbl 0505.65020Karp, Richard M.; Papadimitriou, Christos H. 27 1982 A Monte-Carlo algorithm for estimating the permanent. Zbl 0781.05034Karmarkar, N.; Karp, R.; Lipton, R.; Lovász, László; Luby, M. 26 1993 Complexity and real computation. Foreword by Richard M. Karp. Zbl 0948.68068Blum, Leonore; Cucker, Felipe; Shub, Michael; Smale, Steve 26 1997 Properties of a model for parallel computations: Determinacy, termination, queueing. Zbl 0149.12501Karp, R. M.; Miller, R. E. 26 1966 The efficiency of resolution and Davis-Putnam procedures. Zbl 1004.03048Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael 23 2002 An optimal algorithm for Monte Carlo estimation. Zbl 1112.65300Dagum, Paul; Karp, Richard; Luby, Michael; Ross, Sheldon 22 2000 Rapid identification of repeated patterns in strings, trees and arrays. Zbl 0354.68119Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. 22 1972 Assembly-line balancing-dynamic programming with precedence constraints. Zbl 0126.36201Held, M.; Karp, R.; Shareshian, R. 22 1963 The complexity of parallel search. Zbl 0651.68048Karp, Richard M.; Upfal, Eli; Wigderson, Avi 19 1988 Efficient PRAM simulation on a distributed memory machine. Zbl 0857.68122Karp, R. M.; Luby, M.; Meyer auf der Heide, Friedhelm 18 1996 Competitive analysis of financial games. Zbl 0977.68504El-Yaniv, R.; Fiat, A.; Karp, R.; Turpin, G. 18 1992 Global wire routing in two-dimensional arrays. Zbl 0634.94024Karp, R. M.; Leighton, F. T.; Rivest, R. L.; Thompson, C. D.; Vazirani, U. V.; Vazirani, V. V. 18 1987 Randomized parallel algorithms for backtrack search and branch-and-bound computation. Zbl 0789.68066Karp, Richard M.; Zhang, Yanjun 16 1993 Searching for an optimal path in a tree with random costs. Zbl 0507.68034Karp, Richard M.; Pearl, Judea 15 1983 The complexity of testing whether a graph is a superconcentrator. Zbl 0482.05059Blum, M.; Karp, R. M.; Vornberger, O.; Papadimitriou, C. H.; Yannakakis, M. 13 1981 On the security of ping-pong protocols. Zbl 0537.94012Dolev, D.; Even, S.; Karp, R. M. 13 1982 The rank of sparse random matrices over finite fields. Zbl 0877.15027Blömer, Johannes; Karp, Richard; Welzl, Emo 13 1997 Efficient algorithms for detecting signaling pathways in protein interaction networks. Zbl 1119.92331Scott, Jacob; Ideker, Trey; Karp, Richard M.; Sharan, Roded 13 2005 Sorting and selection in posets. Zbl 1232.68034Daskalakis, Constantinos; Karp, Richard M.; Mossel, Elchanan; Riesenfeld, Samantha J.; Verbin, Elad 13 2011 Probabilistic analysis of optimum partitioning. Zbl 0611.60011Karmarkar, Narendra; Karp, Richard M.; Lueker, George S.; Odlyzko, Andrew M. 12 1986 The probabilistic analysis of some combinatorial search algorithms. Zbl 0368.68035Karp, Richard M. 12 1976 A simple derivation of Edmonds’ algorithm for optimum branchings. Zbl 0229.05127Karp, R. M. 12 1972 On the complexity of unsatisfiability proofs for random \(k\)-CNF formulas. Zbl 1028.68067Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael 12 1998 Parallel minimax search for a maximum. Zbl 0153.47703Karp, Richard M.; Miranker, Willard L. 12 1967 Two special cases of the assignment problem. Zbl 0311.90066Karp, Richard M.; Li, Shuo-Yen R. 12 1975 A criterion for planarity of the square of a graph. Zbl 0153.25902Harary, Frank; Karp, R. M.; Tutte, W. T. 11 1967 Noisy binary search and its applications. Zbl 1302.68107Karp, Richard M.; Kleinberg, Robert 10 2007 A stochastic process on the hypercube with applications to peer-to-peer networks. Zbl 1192.68018Adler, Micah; Halperin, Eran; Karp, Richard M.; Vazirani, Vijay V. 10 2003 Coding techniques for handling failures in large disk arrays. Zbl 1338.68031Hellerstein, L.; Gibson, G. A.; Karp, R. M.; Katz, R. H.; Patterson, D. A. 10 1994 A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps. Zbl 0641.65054Adler, Ilan; Karp, Richard M.; Shamir, Ron 10 1987 Parallel program schemata. Zbl 0369.68013Karp, R. M.; Miller, R. E. 9 1976 Physical mapping of chromosomes using unique probes. Zbl 0870.92005Alizadeh, Farid; Karp, Richard M.; Weisser, Deborah K.; Zweig, Geoffrey 9 1994 On the optimality of Huffman trees. Zbl 0349.05101Glassey, C. R.; Karp, R. M. 8 1976 An algorithm to solve the \(m\times n\) assignment problem in expected time O(mn log n). Zbl 0441.68076Karp, Richard M. 8 1980 Physical mapping of chromosomes: A combinatorial problem in molecular biology. Zbl 0831.92012Alizadeh, F.; Karp, R. M.; Newberg, L. A.; Weisser, D. K. 8 1995 Minimum-redundancy coding for the discrete noiseless channel. Zbl 0099.34402Karp, Richard M. 8 1961 Some bounds on the storage requirements of sequential machines and Turing machines. Zbl 0153.31802Karp, R. M. 8 1967 The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment. Zbl 1267.90125Moreno-Centeno, Erick; Karp, Richard M. 8 2013 A family of simplex variants solving an m\(\times d\) linear program in expected number of pivot steps depending on d only. Zbl 0618.90064Adler, Ilan; Karp, Richard; Shamir, Ron 7 1986 Turing machines that take advice. Zbl 0494.68061Karp, Richard M.; Lipton, Richard J. 7 1982 Probabilistic recurrence relations. Zbl 0830.68046Karp, Richard M. 7 1994 Linear expected-time algorithms for connectivity problems. Zbl 0463.68060Karp, Richard M.; Tarjan, Robert Endre 7 1980 Nearly optimal competitive online replacement policies. Zbl 0894.68076El-Yaniv, Ran; Karp, Richard M. 7 1997 Error-resilient DNA computation. (Preliminary version). Zbl 0846.68034Karp, Richard M.; Kenyon, Claire; Waarts, Orli 7 1996 The minimum-entropy set cover problem. Zbl 1081.94008Halperin, Eran; Karp, Richard M. 7 2005 Graph algorithms. Edited by Guy Even. With a foreword by Richard M. Karp. 2nd ed. Zbl 1237.05199Even, Shimon 7 2012 Near-optimal solutions to a 2-dimensional placement problem. Zbl 0355.68044Karp, R. M.; McKellar, A. C.; Wong, C. K. 6 1975 A method for obtaining randomized algorithms with small tail probabilities. Zbl 0857.68057Alt, H.; Guibas, L.; Mehlhorn, K.; Karp, R.; Wigderson, A. 6 1996 Algorithms for graph partitioning on the planted partition model. Zbl 0946.05081Condon, Anne; Karp, Richard M. 5 1999 An introduction to randomized algorithms. Zbl 0757.68085Karp, Richard M. 5 1991 Mathematical challenges from genomics and molecular biology. Zbl 1126.92309Karp, Richard 5 2002 Probabilistic analysis of partitioning algorithms for the traveling- salesman problem in the plane. Zbl 0391.90090Karp, R. M. 5 1978 Selection in the presence of noise: The design of playoff systems. Zbl 0870.90109Adler, Micah; Gemmell, Peter; Harchol-Balter, Mor; Karp, Richard M.; Kenyon, Claire 5 1994 When is the assignment bound tight for the asymmetric traveling-salesman problem? Zbl 0833.90096Frieze, Alan; Karp, Richard M.; Reed, Bruce 5 1995 Global synchronization in sensornets. Zbl 1196.68024Elson, Jeremy; Karp, Richard M.; Papadimitriou, Christos H.; Shenker, Scott 5 2004 An upper bound on the expected cost of an optimal assignment. Zbl 0639.90066Karp, Richard M. 5 1987 Combinatorics, complexity, and randomness. Zbl 0642.68004Karp, Richard M. 5 1986 Sorting and selection in posets. Zbl 1421.68034Daskalakis, Constantinos; Karp, Richard M.; Mossel, Elchanan; Riesenfeld, Samantha; Verbin, Elad 4 2009 Average case analysis of a heuristic for the assignment problem. Zbl 0813.90122Karp, Richard M.; Rinnooy Kan, Alexander H. G.; Vohra, Rakesh V. 4 1994 Heuristic algorithms in computational molecular biology. Zbl 1210.92003Karp, Richard M. 4 2011 Random knockout tournaments. Zbl 1405.91084Adler, Ilan; Cao, Yang; Karp, Richard; Peköz, Erol A.; Ross, Sheldon M. 3 2017 Probabilistic analysis. Zbl 0588.90062Karp, R. M.; Lenstra, J. K.; McDiarmid, C. J. H.; Rinnooy Kan, A. H. G. 3 1985 Deferred data structuring. Zbl 0662.68017Karp, Richard M.; Motwani, Rajeev; Raghavan, Prabhakar 3 1988 Probabilistic analysis of a canonical numbering algorithm for graphs. Zbl 0428.68052Karp, Richard M. 3 1979 Transitive compaction in parallel via branchings. Zbl 0718.68058Gibbons, Phillip; Karp, Richard; Ramachandran, Vijaya; Soroker, Danny; Tarjan, Robert 3 1991 Coalescing times for IID random variables with applications to population biology. Zbl 1042.60003Adler, Ilan; Ahn, Hyun-Soo; Karp, Richard M.; Ross, Sheldon M. 3 2003 Massively parallel computation of matching and MIS in sparse graphs. Zbl 07298713Behnezhad, Soheil; Brandt, Sebastian; Derakhshan, Mahsa; Fischer, Manuela; Hajiaghayi, MohammadTaghi; Karp, Richard M.; Uitto, Jara 1 2019 Random knockout tournaments. Zbl 1405.91084Adler, Ilan; Cao, Yang; Karp, Richard; Peköz, Erol A.; Ross, Sheldon M. 3 2017 The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment. Zbl 1267.90125Moreno-Centeno, Erick; Karp, Richard M. 8 2013 Graph algorithms. Edited by Guy Even. With a foreword by Richard M. Karp. 2nd ed. Zbl 1237.05199Even, Shimon 7 2012 Sorting and selection in posets. Zbl 1232.68034Daskalakis, Constantinos; Karp, Richard M.; Mossel, Elchanan; Riesenfeld, Samantha J.; Verbin, Elad 13 2011 Heuristic algorithms in computational molecular biology. Zbl 1210.92003Karp, Richard M. 4 2011 Algorithms for implicit hitting set problems. Zbl 1375.68214Chandrasekaran, Karthekeyan; Karp, Richard; Moreno-Centeno, Erick; Vempala, Santosh 1 2011 Reducibility among combinatorial problems. Zbl 1187.90014Karp, Richard M. 34 2010 Sorting and selection in posets. Zbl 1421.68034Daskalakis, Constantinos; Karp, Richard M.; Mossel, Elchanan; Riesenfeld, Samantha; Verbin, Elad 4 2009 Linked decompositions of networks and the power of choice in Pólya urns. Zbl 1192.90027Lin, Henry; Amanatidis, Christos; Sideri, Martha; Karp, Richard M.; Papadimitriou, Christos H. 2 2008 George Dantzig’s impact on the theory of computation. Zbl 1151.90527Karp, Richard M. 1 2008 Noisy binary search and its applications. Zbl 1302.68107Karp, Richard M.; Kleinberg, Robert 10 2007 Efficient algorithms for detecting signaling pathways in protein interaction networks. Zbl 1119.92331Scott, Jacob; Ideker, Trey; Karp, Richard M.; Sharan, Roded 13 2005 The minimum-entropy set cover problem. Zbl 1081.94008Halperin, Eran; Karp, Richard M. 7 2005 A probabilistic model for the survivability of cells. Zbl 1090.92036Adler, Ilan; Ahn, Hyun-Soo; Karp, Richard M.; Ross, Sheldon M. 2 2005 Global synchronization in sensornets. Zbl 1196.68024Elson, Jeremy; Karp, Richard M.; Papadimitriou, Christos H.; Shenker, Scott 5 2004 The minimum-entropy set cover problem. Zbl 1099.94519Halperin, Eran; Karp, Richard M. 2 2004 A stochastic process on the hypercube with applications to peer-to-peer networks. Zbl 1192.68018Adler, Micah; Halperin, Eran; Karp, Richard M.; Vazirani, Vijay V. 10 2003 Coalescing times for IID random variables with applications to population biology. Zbl 1042.60003Adler, Ilan; Ahn, Hyun-Soo; Karp, Richard M.; Ross, Sheldon M. 3 2003 The efficiency of resolution and Davis-Putnam procedures. Zbl 1004.03048Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael 23 2002 Mathematical challenges from genomics and molecular biology. Zbl 1126.92309Karp, Richard 5 2002 Application-level multicast using content-addressable networks. Zbl 1060.68544Ratnasamy, Sylvia; Handley, Mark; Karp, Richard; Shenker, Scott 35 2001 Optimal search and one-way trading online algorithms. Zbl 0984.68043El-Yaniv, R.; Fiat, A.; Karp, R. M.; Turpin, G. 33 2001 Algorithms for graph partitioning on the planted partition model. Zbl 0972.68129Condon, Anne; Karp, Richard M. 28 2001 The genomics revolution and its challenges for algorithmic research. Zbl 1049.68156Karp, Richard M. 1 2001 An optimal algorithm for Monte Carlo estimation. Zbl 1112.65300Dagum, Paul; Karp, Richard; Luby, Michael; Ross, Sheldon 22 2000 Parallel sorting with limited bandwidth. Zbl 0953.68044Adler, Micah; Byers, John W.; Karp, Richard M. 1 2000 Algorithms for graph partitioning on the planted partition model. Zbl 0946.05081Condon, Anne; Karp, Richard M. 5 1999 Error-resilient DNA computation. Zbl 0931.68052Karp, Richard M.; Kenyon, Claire; Waarts, Orli 1 1999 On the complexity of unsatisfiability proofs for random \(k\)-CNF formulas. Zbl 1028.68067Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael 12 1998 Graph traversals, genes and matroids: An efficient case of the travelling salesman problem. Zbl 0927.68061Gusfield, Dan; Karp, Richard; Wang, Lusheng; Stelling, Paul 2 1998 Complexity and real computation. Foreword by Richard M. Karp. Zbl 0948.68068Blum, Leonore; Cucker, Felipe; Shub, Michael; Smale, Steve 26 1997 The rank of sparse random matrices over finite fields. Zbl 0877.15027Blömer, Johannes; Karp, Richard; Welzl, Emo 13 1997 Nearly optimal competitive online replacement policies. Zbl 0894.68076El-Yaniv, Ran; Karp, Richard M. 7 1997 Efficient PRAM simulation on a distributed memory machine. Zbl 0857.68122Karp, R. M.; Luby, M.; Meyer auf der Heide, Friedhelm 18 1996 Error-resilient DNA computation. (Preliminary version). Zbl 0846.68034Karp, Richard M.; Kenyon, Claire; Waarts, Orli 7 1996 A method for obtaining randomized algorithms with small tail probabilities. Zbl 0857.68057Alt, H.; Guibas, L.; Mehlhorn, K.; Karp, R.; Wigderson, A. 6 1996 A graph-theoretic game and its application to the \(k\)-server problem. Zbl 0818.90147Alon, Noga; Karp, Richard M.; Peleg, David; West, Douglas 41 1995 Physical mapping of chromosomes: A combinatorial problem in molecular biology. Zbl 0831.92012Alizadeh, F.; Karp, R. M.; Newberg, L. A.; Weisser, D. K. 8 1995 When is the assignment bound tight for the asymmetric traveling-salesman problem? Zbl 0833.90096Frieze, Alan; Karp, Richard M.; Reed, Bruce 5 1995 Bounded branching process and AND/OR tree evaluation. Zbl 0828.60072Karp, Richard M.; Zhang, Yanjun 1 1995 An optimal algorithm for Monte Carlo estimation. (Extended abstract). Zbl 0938.68910Dagum, Paul; Karp, Richard; Luby, Michael; Ross, Sheldon 1 1995 The bit vector intersection problem. (Preliminary version). Zbl 0938.68933Karp, Richard M.; Waarts, Orli; Zweig, Geoffrey 1 1995 On the power of randomization in on-line algorithms. Zbl 0784.68038Ben-David, S.; Borodin, A.; Karp, R.; Tardos, G.; Wigderson, A. 54 1994 Coding techniques for handling failures in large disk arrays. Zbl 1338.68031Hellerstein, L.; Gibson, G. A.; Karp, R. M.; Katz, R. H.; Patterson, D. A. 10 1994 Physical mapping of chromosomes using unique probes. Zbl 0870.92005Alizadeh, Farid; Karp, Richard M.; Weisser, Deborah K.; Zweig, Geoffrey 9 1994 Probabilistic recurrence relations. Zbl 0830.68046Karp, Richard M. 7 1994 Selection in the presence of noise: The design of playoff systems. Zbl 0870.90109Adler, Micah; Gemmell, Peter; Harchol-Balter, Mor; Karp, Richard M.; Kenyon, Claire 5 1994 Average case analysis of a heuristic for the assignment problem. Zbl 0813.90122Karp, Richard M.; Rinnooy Kan, Alexander H. G.; Vohra, Rakesh V. 4 1994 Mapping the genome, some combinatorial problems arising in molecular biology. Zbl 1310.92022Karp, Richard M. 33 1993 A Monte-Carlo algorithm for estimating the permanent. Zbl 0781.05034Karmarkar, N.; Karp, R.; Lipton, R.; Lovász, László; Luby, M. 26 1993 Randomized parallel algorithms for backtrack search and branch-and-bound computation. Zbl 0789.68066Karp, Richard M.; Zhang, Yanjun 16 1993 Probabilistic analysis of network flow algorithms. Zbl 0780.90039Karp, Richard M.; Motwani, Rajeev; Nisan, Noam 2 1993 Physical mapping of chromosomes: A combinatorial problem in molecular biology. Zbl 0815.92005Alizadeh, Farid; Karp, Richard M.; Newberg, Lee A.; Weisser, Deborah K. 2 1993 Competitive analysis of financial games. Zbl 0977.68504El-Yaniv, R.; Fiat, A.; Karp, R.; Turpin, G. 18 1992 A graph-theoretic game and its application to the \(k\)-server problem. Zbl 0801.68122Alon, Noga; Karp, Richard M.; Peleg, David; West, Douglas 2 1992 Three-stage generalized connectors. Zbl 0752.94022Karp, Richard M. 1 1992 Competitive paging algorithms. Zbl 0753.68018Fiat, Amos; Karp, Richard M.; Luby, Michael; McGeoch, Lyle A.; Sleator, Daniel D.; Young, Neal E. 59 1991 An introduction to randomized algorithms. Zbl 0757.68085Karp, Richard M. 5 1991 Transitive compaction in parallel via branchings. Zbl 0718.68058Gibbons, Phillip; Karp, Richard; Ramachandran, Vijaya; Soroker, Danny; Tarjan, Robert 3 1991 Parallel algorithms for shared-memory machines. Zbl 0900.68267Karp, Richard M.; Ramachandran, Vijaya 179 1990 The transitive closure of a random digraph. Zbl 0712.68076Karp, Richard M. 51 1990 Subtree isomorphism is in random NC. Zbl 0711.68052Gibbons, Phillip B.; Karp, Richard M.; Miller, Gary L.; Soroker, Danny 1 1990 Monte-Carlo approximation algorithms for enumeration problems. Zbl 0678.65001Karp, Richard M.; Luby, Michael; Madras, Neal 46 1989 The complexity of parallel search. Zbl 0651.68048Karp, Richard M.; Upfal, Eli; Wigderson, Avi 19 1988 Deferred data structuring. Zbl 0662.68017Karp, Richard M.; Motwani, Rajeev; Raghavan, Prabhakar 3 1988 Subtree isomorphism is in random NC. Zbl 0652.68078Gibbons, Phillip B.; Miller, Gary L.; Karp, Richard M.; Soroker, Danny 1 1988 Efficient randomized pattern-matching algorithms. Zbl 0653.68054Karp, Richard M.; Rabin, Michael O. 105 1987 Global wire routing in two-dimensional arrays. Zbl 0634.94024Karp, R. M.; Leighton, F. T.; Rivest, R. L.; Thompson, C. D.; Vazirani, U. V.; Vazirani, V. V. 18 1987 A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps. Zbl 0641.65054Adler, Ilan; Karp, Richard M.; Shamir, Ron 10 1987 An upper bound on the expected cost of an optimal assignment. Zbl 0639.90066Karp, Richard M. 5 1987 Constructing a perfect matching is in random NC. Zbl 0646.05051Karp, R. M.; Upfal, E.; Wigderson, A. 55 1986 Probabilistic analysis of optimum partitioning. Zbl 0611.60011Karmarkar, Narendra; Karp, Richard M.; Lueker, George S.; Odlyzko, Andrew M. 12 1986 A family of simplex variants solving an m\(\times d\) linear program in expected number of pivot steps depending on d only. Zbl 0618.90064Adler, Ilan; Karp, Richard; Shamir, Ron 7 1986 Combinatorics, complexity, and randomness. Zbl 0642.68004Karp, Richard M. 5 1986 A fast parallel algorithm for the maximal independent set problem. Zbl 0633.68026Karp, Richard M.; Wigderson, Avi 46 1985 Monte-Carlo algorithms for the planar multiterminal network reliability problem. Zbl 0596.90033Karp, Richard M.; Luby, Michael 35 1985 Probabilistic analysis of heuristics. Zbl 0582.90100Karp, R. M.; Steele, J. M. 30 1985 Probabilistic analysis. Zbl 0588.90062Karp, R. M.; Lenstra, J. K.; McDiarmid, C. J. H.; Rinnooy Kan, A. H. G. 3 1985 Searching for an optimal path in a tree with random costs. Zbl 0507.68034Karp, Richard M.; Pearl, Judea 15 1983 On the security of ping-pong protocols. Zbl 0514.94012Dolev, D.; Even, S.; Karp, R. M. 2 1983 Search and heuristics. In memory of John Gaschnig. (Repr. from the Journal “Artificial Intelligence”, Vol. 21, Nos. 1, 2). Zbl 0522.68088 1 1983 Turing machines that take advice. Zbl 0529.68025Karp, Richard M.; Lipton, Richard J. 59 1982 Dynamic programming meets the principle of inclusion and exclusion. Zbl 0486.90083Karp, Richard M. 32 1982 On linear characterizations of combinatorial optimization problems. Zbl 0505.65020Karp, Richard M.; Papadimitriou, Christos H. 27 1982 On the security of ping-pong protocols. Zbl 0537.94012Dolev, D.; Even, S.; Karp, R. M. 13 1982 Turing machines that take advice. Zbl 0494.68061Karp, Richard M.; Lipton, Richard J. 7 1982 Parametric shortest path algorithms with an application to cyclic staffing. Zbl 0453.68032Karp, Richard M.; Orlin, James B. 29 1981 The complexity of testing whether a graph is a superconcentrator. Zbl 0482.05059Blum, M.; Karp, R. M.; Vornberger, O.; Papadimitriou, C. H.; Yannakakis, M. 13 1981 An algorithm to solve the \(m\times n\) assignment problem in expected time O(mn log n). Zbl 0441.68076Karp, Richard M. 8 1980 Linear expected-time algorithms for connectivity problems. Zbl 0463.68060Karp, Richard M.; Tarjan, Robert Endre 7 1980 A patching algorithm for the nonsymmetric traveling-salesman problem. Zbl 0427.90064Karp, Richard M. 49 1979 Probabilistic analysis of a canonical numbering algorithm for graphs. Zbl 0428.68052Karp, Richard M. 3 1979 A characterization of the minimum cycle mean in a digraph. Zbl 0386.05032Karp, Richard M. 173 1978 Probabilistic analysis of partitioning algorithms for the traveling- salesman problem in the plane. Zbl 0391.90090Karp, R. M. 5 1978 Probabilistic analysis of partitioning algorithms for the traveling- salesman problem in the plane. Zbl 0391.90091Karp, Richard M. 70 1977 The probabilistic analysis of some combinatorial search algorithms. Zbl 0368.68035Karp, Richard M. 12 1976 Parallel program schemata. Zbl 0369.68013Karp, R. M.; Miller, R. E. 9 1976 On the optimality of Huffman trees. Zbl 0349.05101Glassey, C. R.; Karp, R. M. 8 1976 Reducibility among combinatorial problems. Zbl 0366.68041Karp, R. M. 692 1975 ...and 27 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 6,207 Authors 21 Chentsov, Aleksandr Georgievich 18 Orlin, James B. 18 Spirakis, Paul G. 17 Paulusma, Daniël 15 Fomin, Fedor V. 15 Gurvich, Vladimir A. 15 Karp, Richard Manning 14 Boros, Endre 14 Chatterjee, Krishnendu 14 Elbassioni, Khaled M. 14 Frieze, Alan Michael 14 Landau, Gad M. 13 Butkovič, Peter 13 Golovach, Petr A. 13 Karpinski, Marek 12 Pan, Victor Yakovlevich 12 Pardalos, Panos M. 12 Saurabh, Saket 12 Woeginger, Gerhard Johannes 11 Bodlaender, Hans L. 11 Bollobás, Béla 11 Boysen, Nils 11 Hamacher, Horst W. 11 Hochbaum, Dorit S. 11 Laporte, Gilbert 11 Maffioli, Francesco 11 Paschos, Vangelis Th. 11 Rizzi, Romeo 11 Rosier, Louis E. 11 Xu, Yinfeng 10 Burkard, Rainer E. 10 Chen, Zhizhong 10 Galil, Zvi 10 Howell, Rodney R. 10 Kobayashi, Yusuke 10 Lingas, Andrzej 10 Makino, Kazuhisa 10 Papadimitriou, Christos Harilaos 10 Tarjan, Robert Endre 9 Chentsov, Pavel Aleksandrovich 9 Colbourn, Charles J. 9 Escudero, Laureano Fernando 9 Evans, David John 9 Finkel, Alain 9 Fiorini, Samuel 9 Ibaraki, Toshihide 9 Kratsch, Dieter 9 Letchford, Adam N. 9 Lokshtanov, Daniel 9 Lorena, Luiz Antonio Nogueira 9 Manthey, Bodo 9 Marchetti-Spaccamela, Alberto 9 Minoux, Michel Andre 9 Niedermeier, Rolf 9 Plavka, Ján 9 Sgall, Jiří 9 Toth, Paolo 9 Williamson, David P. 8 Albers, Susanne 8 Alon, Noga M. 8 Amir, Amihood 8 Bartal, Yair 8 Bille, Philip 8 Cheng, Tai-Chiu Edwin 8 Gabow, Harold N. 8 Gawrychowski, Paweł 8 Glover, Fred W. 8 Gušev, Marjan 8 Hougardy, Stefan 8 Lenstra, Jan Karel 8 Luby, Michael G. 8 Protti, Fábio 8 Ramachandran, Vijaya 8 Reif, John H. 8 Vygen, Jens 8 Wigderson, Avi 7 Arkin, Esther M. 7 Belazzougui, Djamal 7 Cardinal, Jean 7 Corneil, Derek Gordon 7 Cygan, Marek 7 Filar, Jerzy A. 7 Grossi, Roberto 7 Havet, Frédéric 7 Jansen, Klaus 7 Johnson, David Stifler 7 Kawarabayashi, Ken-ichi 7 Levin, Asaf 7 Mehlhorn, Kurt 7 Mitchell, Joseph S. B. 7 Park, Kunsoo 7 Pirkul, Hasan 7 Pittel, Boris G. 7 Rinnooy Kan, Alexander Hendrik George 7 Steiner, George 7 Van Leeuwen, Erik Jan 7 Vazirani, Vijay V. 7 Vialette, Stéphane 7 Yukna, Stasys P. 7 Zheng, Feifeng ...and 6,107 more Authors all top 5 Cited in 396 Serials 429 Theoretical Computer Science 318 Discrete Applied Mathematics 265 European Journal of Operational Research 238 Information Processing Letters 192 Algorithmica 166 Journal of Computer and System Sciences 118 Computers & Operations Research 96 Operations Research Letters 77 Discrete Mathematics 77 Mathematical Programming. Series A. Series B 65 Information and Computation 49 Mathematical Programming 43 Theory of Computing Systems 41 Artificial Intelligence 41 Annals of Operations Research 38 Journal of Discrete Algorithms 37 Random Structures & Algorithms 36 Journal of Combinatorial Optimization 35 Linear Algebra and its Applications 34 SIAM Journal on Computing 34 Discrete Optimization 28 Information Sciences 28 Networks 27 Combinatorica 26 Journal of Combinatorial Theory. Series B 25 SIAM Journal on Discrete Mathematics 23 Applied Mathematics and Computation 22 Acta Informatica 22 International Journal of Computer Mathematics 21 Distributed Computing 19 Journal of Scheduling 18 Journal of Complexity 17 Automatica 17 Parallel Algorithms and Applications 15 Computers & Mathematics with Applications 15 Journal of Optimization Theory and Applications 15 Mathematical and Computer Modelling 15 Combinatorics, Probability and Computing 14 Computational Geometry 14 International Journal of Foundations of Computer Science 14 Computational Optimization and Applications 14 Constraints 13 Journal of Mathematical Analysis and Applications 13 Computing 13 Mathematical Systems Theory 13 SIAM Journal on Algebraic and Discrete Methods 13 Discrete Event Dynamic Systems 12 Journal of Parallel and Distributed Computing 12 Computational Complexity 11 Discrete & Computational Geometry 11 Journal of Global Optimization 11 Automation and Remote Control 11 Cybernetics and Systems Analysis 10 Optimization 10 Graphs and Combinatorics 10 Computer Science Review 9 Journal of Statistical Physics 9 Journal of Computational and Applied Mathematics 9 Journal of Soviet Mathematics 9 European Journal of Combinatorics 9 International Journal of Approximate Reasoning 9 Top 9 Annals of Mathematics and Artificial Intelligence 9 RAIRO. Operations Research 9 Optimization Letters 9 Algorithms 8 Kybernetika 8 International Journal of Production Research 8 Journal of Automated Reasoning 8 RAIRO. Informatique Théorique et Applications 8 Mathematical Methods of Operations Research 7 The Annals of Statistics 7 Calcolo 7 Operations Research 7 RAIRO, Informatique Théorique 7 Cybernetics 7 Annals of Pure and Applied Logic 7 Asia-Pacific Journal of Operational Research 7 Games and Economic Behavior 7 Pattern Recognition 7 ZOR. Zeitschrift für Operations Research 7 Mathematical Problems in Engineering 7 Journal of Graph Algorithms and Applications 7 CEJOR. Central European Journal of Operations Research 7 Natural Computing 7 4OR 7 Logical Methods in Computer Science 7 Mathematical Programming Computation 6 Journal of the Franklin Institute 6 Journal of Symbolic Computation 6 Zeitschrift für Operations Research. Serie A: Theorie 6 Formal Methods in System Design 6 INFORMS Journal on Computing 6 Naval Research Logistics Quarterly 5 International Journal of Systems Science 5 Physica A 5 International Journal of Computer & Information Sciences 5 Journal of Combinatorial Theory. Series A 5 Mathematics of Operations Research 5 Numerische Mathematik ...and 296 more Serials all top 5 Cited in 53 Fields 2,340 Computer science (68-XX) 1,609 Operations research, mathematical programming (90-XX) 1,130 Combinatorics (05-XX) 291 Numerical analysis (65-XX) 241 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 141 Mathematical logic and foundations (03-XX) 123 Information and communication theory, circuits (94-XX) 98 Biology and other natural sciences (92-XX) 97 Probability theory and stochastic processes (60-XX) 90 Statistics (62-XX) 86 Linear and multilinear algebra; matrix theory (15-XX) 70 Systems theory; control (93-XX) 41 Convex and discrete geometry (52-XX) 32 Calculus of variations and optimal control; optimization (49-XX) 31 Number theory (11-XX) 29 Statistical mechanics, structure of matter (82-XX) 27 Order, lattices, ordered algebraic structures (06-XX) 17 Quantum theory (81-XX) 16 Group theory and generalizations (20-XX) 13 Field theory and polynomials (12-XX) 13 Dynamical systems and ergodic theory (37-XX) 8 Commutative algebra (13-XX) 8 Ordinary differential equations (34-XX) 8 Geometry (51-XX) 7 History and biography (01-XX) 6 General and overarching topics; collections (00-XX) 6 Measure and integration (28-XX) 5 Algebraic geometry (14-XX) 5 Functions of a complex variable (30-XX) 5 General topology (54-XX) 5 Manifolds and cell complexes (57-XX) 5 Mechanics of deformable solids (74-XX) 4 Real functions (26-XX) 4 Partial differential equations (35-XX) 4 Functional analysis (46-XX) 4 Operator theory (47-XX) 3 General algebraic systems (08-XX) 3 Approximations and expansions (41-XX) 3 Algebraic topology (55-XX) 3 Global analysis, analysis on manifolds (58-XX) 2 Associative rings and algebras (16-XX) 2 Category theory; homological algebra (18-XX) 2 Difference and functional equations (39-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 2 Differential geometry (53-XX) 1 Nonassociative rings and algebras (17-XX) 1 Sequences, series, summability (40-XX) 1 Integral transforms, operational calculus (44-XX) 1 Mechanics of particles and systems (70-XX) 1 Fluid mechanics (76-XX) 1 Optics, electromagnetic theory (78-XX) 1 Geophysics (86-XX) 1 Mathematics education (97-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.