×

Karp, Richard Manning

Compute Distance To:
Author ID: karp.richard-m Recent zbMATH articles by "Karp, Richard Manning"
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)
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

Publications by Year

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.68041
Karp, R. M.
692
1975
A \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. Zbl 0266.05114
Hopcroft, John E.; Karp, Richard M.
408
1973
Theoretical improvements in algorithmic efficiency for network flow problems. Zbl 0318.90024
Edmonds, Jack; Karp, Richard M.
324
1972
The traveling-salesman problem and minimum spanning trees. Zbl 0226.90047
Held, Michael; Karp, Richard M.
233
1970
A dynamic programming approach to sequencing problems. Zbl 0106.14103
Held, Michael; Karp, Richard M.
232
1962
The traveling-salesman problem and minimum spanning trees. II. Zbl 0232.90038
Held, Michael; Karp, Richard M.
198
1971
Parallel algorithms for shared-memory machines. Zbl 0900.68267
Karp, Richard M.; Ramachandran, Vijaya
179
1990
Parallel program schemata. Zbl 0198.32603
Karp, Richard M.; Miller, Raymond E.
174
1969
A characterization of the minimum cycle mean in a digraph. Zbl 0386.05032
Karp, Richard M.
173
1978
Reducibility among combinatorial problems. Zbl 1467.68065
Karp, Richard M.
144
1972
On the computational complexity of combinatorial problems. Zbl 0324.05003
Karp, R. M.
128
1975
Efficient randomized pattern-matching algorithms. Zbl 0653.68054
Karp, Richard M.; Rabin, Michael O.
105
1987
Probabilistic analysis of partitioning algorithms for the traveling- salesman problem in the plane. Zbl 0391.90091
Karp, Richard M.
70
1977
On nonterminating stochastic games. Zbl 0136.14303
Hoffman, A. J.; Karp, R. M.
68
1966
Turing machines that take advice. Zbl 0529.68025
Karp, Richard M.; Lipton, Richard J.
59
1982
Competitive paging algorithms. Zbl 0753.68018
Fiat, 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.05051
Karp, R. M.; Upfal, E.; Wigderson, A.
55
1986
On the power of randomization in on-line algorithms. Zbl 0784.68038
Ben-David, S.; Borodin, A.; Karp, R.; Tardos, G.; Wigderson, A.
54
1994
The transitive closure of a random digraph. Zbl 0712.68076
Karp, Richard M.
51
1990
A patching algorithm for the nonsymmetric traveling-salesman problem. Zbl 0427.90064
Karp, Richard M.
49
1979
The organization of computations for uniform recurrence equations. Zbl 0171.38305
Karp, Richard M.; Miller, Raymond E.; Winograd, Shmuel
49
1967
Monte-Carlo approximation algorithms for enumeration problems. Zbl 0678.65001
Karp, Richard M.; Luby, Michael; Madras, Neal
46
1989
A fast parallel algorithm for the maximal independent set problem. Zbl 0633.68026
Karp, Richard M.; Wigderson, Avi
46
1985
Finite-state processes and dynamic programming. Zbl 0155.28701
Karp, R. M.; Held, M.
42
1967
A graph-theoretic game and its application to the \(k\)-server problem. Zbl 0818.90147
Alon, Noga; Karp, Richard M.; Peleg, David; West, Douglas
41
1995
Application-level multicast using content-addressable networks. Zbl 1060.68544
Ratnasamy, Sylvia; Handley, Mark; Karp, Richard; Shenker, Scott
35
2001
Monte-Carlo algorithms for the planar multiterminal network reliability problem. Zbl 0596.90033
Karp, Richard M.; Luby, Michael
35
1985
Reducibility among combinatorial problems. Zbl 1187.90014
Karp, Richard M.
34
2010
Optimal search and one-way trading online algorithms. Zbl 0984.68043
El-Yaniv, R.; Fiat, A.; Karp, R. M.; Turpin, G.
33
2001
Mapping the genome, some combinatorial problems arising in molecular biology. Zbl 1310.92022
Karp, Richard M.
33
1993
Dynamic programming meets the principle of inclusion and exclusion. Zbl 0486.90083
Karp, Richard M.
32
1982
Probabilistic analysis of heuristics. Zbl 0582.90100
Karp, R. M.; Steele, J. M.
30
1985
Parametric shortest path algorithms with an application to cyclic staffing. Zbl 0453.68032
Karp, Richard M.; Orlin, James B.
29
1981
Algorithms for graph partitioning on the planted partition model. Zbl 0972.68129
Condon, Anne; Karp, Richard M.
28
2001
On linear characterizations of combinatorial optimization problems. Zbl 0505.65020
Karp, Richard M.; Papadimitriou, Christos H.
27
1982
A Monte-Carlo algorithm for estimating the permanent. Zbl 0781.05034
Karmarkar, N.; Karp, R.; Lipton, R.; Lovász, László; Luby, M.
26
1993
Complexity and real computation. Foreword by Richard M. Karp. Zbl 0948.68068
Blum, Leonore; Cucker, Felipe; Shub, Michael; Smale, Steve
26
1997
Properties of a model for parallel computations: Determinacy, termination, queueing. Zbl 0149.12501
Karp, R. M.; Miller, R. E.
26
1966
The efficiency of resolution and Davis-Putnam procedures. Zbl 1004.03048
Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael
23
2002
An optimal algorithm for Monte Carlo estimation. Zbl 1112.65300
Dagum, Paul; Karp, Richard; Luby, Michael; Ross, Sheldon
22
2000
Rapid identification of repeated patterns in strings, trees and arrays. Zbl 0354.68119
Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L.
22
1972
Assembly-line balancing-dynamic programming with precedence constraints. Zbl 0126.36201
Held, M.; Karp, R.; Shareshian, R.
22
1963
The complexity of parallel search. Zbl 0651.68048
Karp, Richard M.; Upfal, Eli; Wigderson, Avi
19
1988
Efficient PRAM simulation on a distributed memory machine. Zbl 0857.68122
Karp, R. M.; Luby, M.; Meyer auf der Heide, Friedhelm
18
1996
Competitive analysis of financial games. Zbl 0977.68504
El-Yaniv, R.; Fiat, A.; Karp, R.; Turpin, G.
18
1992
Global wire routing in two-dimensional arrays. Zbl 0634.94024
Karp, 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.68066
Karp, Richard M.; Zhang, Yanjun
16
1993
Searching for an optimal path in a tree with random costs. Zbl 0507.68034
Karp, Richard M.; Pearl, Judea
15
1983
The complexity of testing whether a graph is a superconcentrator. Zbl 0482.05059
Blum, M.; Karp, R. M.; Vornberger, O.; Papadimitriou, C. H.; Yannakakis, M.
13
1981
On the security of ping-pong protocols. Zbl 0537.94012
Dolev, D.; Even, S.; Karp, R. M.
13
1982
The rank of sparse random matrices over finite fields. Zbl 0877.15027
Blömer, Johannes; Karp, Richard; Welzl, Emo
13
1997
Efficient algorithms for detecting signaling pathways in protein interaction networks. Zbl 1119.92331
Scott, Jacob; Ideker, Trey; Karp, Richard M.; Sharan, Roded
13
2005
Sorting and selection in posets. Zbl 1232.68034
Daskalakis, Constantinos; Karp, Richard M.; Mossel, Elchanan; Riesenfeld, Samantha J.; Verbin, Elad
13
2011
Probabilistic analysis of optimum partitioning. Zbl 0611.60011
Karmarkar, Narendra; Karp, Richard M.; Lueker, George S.; Odlyzko, Andrew M.
12
1986
The probabilistic analysis of some combinatorial search algorithms. Zbl 0368.68035
Karp, Richard M.
12
1976
A simple derivation of Edmonds’ algorithm for optimum branchings. Zbl 0229.05127
Karp, R. M.
12
1972
On the complexity of unsatisfiability proofs for random \(k\)-CNF formulas. Zbl 1028.68067
Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael
12
1998
Parallel minimax search for a maximum. Zbl 0153.47703
Karp, Richard M.; Miranker, Willard L.
12
1967
Two special cases of the assignment problem. Zbl 0311.90066
Karp, Richard M.; Li, Shuo-Yen R.
12
1975
A criterion for planarity of the square of a graph. Zbl 0153.25902
Harary, Frank; Karp, R. M.; Tutte, W. T.
11
1967
Noisy binary search and its applications. Zbl 1302.68107
Karp, Richard M.; Kleinberg, Robert
10
2007
A stochastic process on the hypercube with applications to peer-to-peer networks. Zbl 1192.68018
Adler, Micah; Halperin, Eran; Karp, Richard M.; Vazirani, Vijay V.
10
2003
Coding techniques for handling failures in large disk arrays. Zbl 1338.68031
Hellerstein, 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.65054
Adler, Ilan; Karp, Richard M.; Shamir, Ron
10
1987
Parallel program schemata. Zbl 0369.68013
Karp, R. M.; Miller, R. E.
9
1976
Physical mapping of chromosomes using unique probes. Zbl 0870.92005
Alizadeh, Farid; Karp, Richard M.; Weisser, Deborah K.; Zweig, Geoffrey
9
1994
On the optimality of Huffman trees. Zbl 0349.05101
Glassey, 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.68076
Karp, Richard M.
8
1980
Physical mapping of chromosomes: A combinatorial problem in molecular biology. Zbl 0831.92012
Alizadeh, F.; Karp, R. M.; Newberg, L. A.; Weisser, D. K.
8
1995
Minimum-redundancy coding for the discrete noiseless channel. Zbl 0099.34402
Karp, Richard M.
8
1961
Some bounds on the storage requirements of sequential machines and Turing machines. Zbl 0153.31802
Karp, R. M.
8
1967
The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment. Zbl 1267.90125
Moreno-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.90064
Adler, Ilan; Karp, Richard; Shamir, Ron
7
1986
Turing machines that take advice. Zbl 0494.68061
Karp, Richard M.; Lipton, Richard J.
7
1982
Probabilistic recurrence relations. Zbl 0830.68046
Karp, Richard M.
7
1994
Linear expected-time algorithms for connectivity problems. Zbl 0463.68060
Karp, Richard M.; Tarjan, Robert Endre
7
1980
Nearly optimal competitive online replacement policies. Zbl 0894.68076
El-Yaniv, Ran; Karp, Richard M.
7
1997
Error-resilient DNA computation. (Preliminary version). Zbl 0846.68034
Karp, Richard M.; Kenyon, Claire; Waarts, Orli
7
1996
The minimum-entropy set cover problem. Zbl 1081.94008
Halperin, Eran; Karp, Richard M.
7
2005
Graph algorithms. Edited by Guy Even. With a foreword by Richard M. Karp. 2nd ed. Zbl 1237.05199
Even, Shimon
7
2012
Near-optimal solutions to a 2-dimensional placement problem. Zbl 0355.68044
Karp, R. M.; McKellar, A. C.; Wong, C. K.
6
1975
A method for obtaining randomized algorithms with small tail probabilities. Zbl 0857.68057
Alt, H.; Guibas, L.; Mehlhorn, K.; Karp, R.; Wigderson, A.
6
1996
Algorithms for graph partitioning on the planted partition model. Zbl 0946.05081
Condon, Anne; Karp, Richard M.
5
1999
An introduction to randomized algorithms. Zbl 0757.68085
Karp, Richard M.
5
1991
Mathematical challenges from genomics and molecular biology. Zbl 1126.92309
Karp, Richard
5
2002
Probabilistic analysis of partitioning algorithms for the traveling- salesman problem in the plane. Zbl 0391.90090
Karp, R. M.
5
1978
Selection in the presence of noise: The design of playoff systems. Zbl 0870.90109
Adler, 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.90096
Frieze, Alan; Karp, Richard M.; Reed, Bruce
5
1995
Global synchronization in sensornets. Zbl 1196.68024
Elson, Jeremy; Karp, Richard M.; Papadimitriou, Christos H.; Shenker, Scott
5
2004
An upper bound on the expected cost of an optimal assignment. Zbl 0639.90066
Karp, Richard M.
5
1987
Combinatorics, complexity, and randomness. Zbl 0642.68004
Karp, Richard M.
5
1986
Sorting and selection in posets. Zbl 1421.68034
Daskalakis, Constantinos; Karp, Richard M.; Mossel, Elchanan; Riesenfeld, Samantha; Verbin, Elad
4
2009
Average case analysis of a heuristic for the assignment problem. Zbl 0813.90122
Karp, Richard M.; Rinnooy Kan, Alexander H. G.; Vohra, Rakesh V.
4
1994
Heuristic algorithms in computational molecular biology. Zbl 1210.92003
Karp, Richard M.
4
2011
Random knockout tournaments. Zbl 1405.91084
Adler, Ilan; Cao, Yang; Karp, Richard; Peköz, Erol A.; Ross, Sheldon M.
3
2017
Probabilistic analysis. Zbl 0588.90062
Karp, R. M.; Lenstra, J. K.; McDiarmid, C. J. H.; Rinnooy Kan, A. H. G.
3
1985
Deferred data structuring. Zbl 0662.68017
Karp, Richard M.; Motwani, Rajeev; Raghavan, Prabhakar
3
1988
Probabilistic analysis of a canonical numbering algorithm for graphs. Zbl 0428.68052
Karp, Richard M.
3
1979
Transitive compaction in parallel via branchings. Zbl 0718.68058
Gibbons, Phillip; Karp, Richard; Ramachandran, Vijaya; Soroker, Danny; Tarjan, Robert
3
1991
Coalescing times for IID random variables with applications to population biology. Zbl 1042.60003
Adler, Ilan; Ahn, Hyun-Soo; Karp, Richard M.; Ross, Sheldon M.
3
2003
Massively parallel computation of matching and MIS in sparse graphs. Zbl 07298713
Behnezhad, Soheil; Brandt, Sebastian; Derakhshan, Mahsa; Fischer, Manuela; Hajiaghayi, MohammadTaghi; Karp, Richard M.; Uitto, Jara
1
2019
Random knockout tournaments. Zbl 1405.91084
Adler, 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.90125
Moreno-Centeno, Erick; Karp, Richard M.
8
2013
Graph algorithms. Edited by Guy Even. With a foreword by Richard M. Karp. 2nd ed. Zbl 1237.05199
Even, Shimon
7
2012
Sorting and selection in posets. Zbl 1232.68034
Daskalakis, Constantinos; Karp, Richard M.; Mossel, Elchanan; Riesenfeld, Samantha J.; Verbin, Elad
13
2011
Heuristic algorithms in computational molecular biology. Zbl 1210.92003
Karp, Richard M.
4
2011
Algorithms for implicit hitting set problems. Zbl 1375.68214
Chandrasekaran, Karthekeyan; Karp, Richard; Moreno-Centeno, Erick; Vempala, Santosh
1
2011
Reducibility among combinatorial problems. Zbl 1187.90014
Karp, Richard M.
34
2010
Sorting and selection in posets. Zbl 1421.68034
Daskalakis, 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.90027
Lin, Henry; Amanatidis, Christos; Sideri, Martha; Karp, Richard M.; Papadimitriou, Christos H.
2
2008
George Dantzig’s impact on the theory of computation. Zbl 1151.90527
Karp, Richard M.
1
2008
Noisy binary search and its applications. Zbl 1302.68107
Karp, Richard M.; Kleinberg, Robert
10
2007
Efficient algorithms for detecting signaling pathways in protein interaction networks. Zbl 1119.92331
Scott, Jacob; Ideker, Trey; Karp, Richard M.; Sharan, Roded
13
2005
The minimum-entropy set cover problem. Zbl 1081.94008
Halperin, Eran; Karp, Richard M.
7
2005
A probabilistic model for the survivability of cells. Zbl 1090.92036
Adler, Ilan; Ahn, Hyun-Soo; Karp, Richard M.; Ross, Sheldon M.
2
2005
Global synchronization in sensornets. Zbl 1196.68024
Elson, Jeremy; Karp, Richard M.; Papadimitriou, Christos H.; Shenker, Scott
5
2004
The minimum-entropy set cover problem. Zbl 1099.94519
Halperin, Eran; Karp, Richard M.
2
2004
A stochastic process on the hypercube with applications to peer-to-peer networks. Zbl 1192.68018
Adler, Micah; Halperin, Eran; Karp, Richard M.; Vazirani, Vijay V.
10
2003
Coalescing times for IID random variables with applications to population biology. Zbl 1042.60003
Adler, Ilan; Ahn, Hyun-Soo; Karp, Richard M.; Ross, Sheldon M.
3
2003
The efficiency of resolution and Davis-Putnam procedures. Zbl 1004.03048
Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael
23
2002
Mathematical challenges from genomics and molecular biology. Zbl 1126.92309
Karp, Richard
5
2002
Application-level multicast using content-addressable networks. Zbl 1060.68544
Ratnasamy, Sylvia; Handley, Mark; Karp, Richard; Shenker, Scott
35
2001
Optimal search and one-way trading online algorithms. Zbl 0984.68043
El-Yaniv, R.; Fiat, A.; Karp, R. M.; Turpin, G.
33
2001
Algorithms for graph partitioning on the planted partition model. Zbl 0972.68129
Condon, Anne; Karp, Richard M.
28
2001
The genomics revolution and its challenges for algorithmic research. Zbl 1049.68156
Karp, Richard M.
1
2001
An optimal algorithm for Monte Carlo estimation. Zbl 1112.65300
Dagum, Paul; Karp, Richard; Luby, Michael; Ross, Sheldon
22
2000
Parallel sorting with limited bandwidth. Zbl 0953.68044
Adler, Micah; Byers, John W.; Karp, Richard M.
1
2000
Algorithms for graph partitioning on the planted partition model. Zbl 0946.05081
Condon, Anne; Karp, Richard M.
5
1999
Error-resilient DNA computation. Zbl 0931.68052
Karp, Richard M.; Kenyon, Claire; Waarts, Orli
1
1999
On the complexity of unsatisfiability proofs for random \(k\)-CNF formulas. Zbl 1028.68067
Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael
12
1998
Graph traversals, genes and matroids: An efficient case of the travelling salesman problem. Zbl 0927.68061
Gusfield, Dan; Karp, Richard; Wang, Lusheng; Stelling, Paul
2
1998
Complexity and real computation. Foreword by Richard M. Karp. Zbl 0948.68068
Blum, Leonore; Cucker, Felipe; Shub, Michael; Smale, Steve
26
1997
The rank of sparse random matrices over finite fields. Zbl 0877.15027
Blömer, Johannes; Karp, Richard; Welzl, Emo
13
1997
Nearly optimal competitive online replacement policies. Zbl 0894.68076
El-Yaniv, Ran; Karp, Richard M.
7
1997
Efficient PRAM simulation on a distributed memory machine. Zbl 0857.68122
Karp, R. M.; Luby, M.; Meyer auf der Heide, Friedhelm
18
1996
Error-resilient DNA computation. (Preliminary version). Zbl 0846.68034
Karp, Richard M.; Kenyon, Claire; Waarts, Orli
7
1996
A method for obtaining randomized algorithms with small tail probabilities. Zbl 0857.68057
Alt, 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.90147
Alon, Noga; Karp, Richard M.; Peleg, David; West, Douglas
41
1995
Physical mapping of chromosomes: A combinatorial problem in molecular biology. Zbl 0831.92012
Alizadeh, 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.90096
Frieze, Alan; Karp, Richard M.; Reed, Bruce
5
1995
Bounded branching process and AND/OR tree evaluation. Zbl 0828.60072
Karp, Richard M.; Zhang, Yanjun
1
1995
An optimal algorithm for Monte Carlo estimation. (Extended abstract). Zbl 0938.68910
Dagum, Paul; Karp, Richard; Luby, Michael; Ross, Sheldon
1
1995
The bit vector intersection problem. (Preliminary version). Zbl 0938.68933
Karp, Richard M.; Waarts, Orli; Zweig, Geoffrey
1
1995
On the power of randomization in on-line algorithms. Zbl 0784.68038
Ben-David, S.; Borodin, A.; Karp, R.; Tardos, G.; Wigderson, A.
54
1994
Coding techniques for handling failures in large disk arrays. Zbl 1338.68031
Hellerstein, L.; Gibson, G. A.; Karp, R. M.; Katz, R. H.; Patterson, D. A.
10
1994
Physical mapping of chromosomes using unique probes. Zbl 0870.92005
Alizadeh, Farid; Karp, Richard M.; Weisser, Deborah K.; Zweig, Geoffrey
9
1994
Probabilistic recurrence relations. Zbl 0830.68046
Karp, Richard M.
7
1994
Selection in the presence of noise: The design of playoff systems. Zbl 0870.90109
Adler, 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.90122
Karp, Richard M.; Rinnooy Kan, Alexander H. G.; Vohra, Rakesh V.
4
1994
Mapping the genome, some combinatorial problems arising in molecular biology. Zbl 1310.92022
Karp, Richard M.
33
1993
A Monte-Carlo algorithm for estimating the permanent. Zbl 0781.05034
Karmarkar, 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.68066
Karp, Richard M.; Zhang, Yanjun
16
1993
Probabilistic analysis of network flow algorithms. Zbl 0780.90039
Karp, Richard M.; Motwani, Rajeev; Nisan, Noam
2
1993
Physical mapping of chromosomes: A combinatorial problem in molecular biology. Zbl 0815.92005
Alizadeh, Farid; Karp, Richard M.; Newberg, Lee A.; Weisser, Deborah K.
2
1993
Competitive analysis of financial games. Zbl 0977.68504
El-Yaniv, R.; Fiat, A.; Karp, R.; Turpin, G.
18
1992
A graph-theoretic game and its application to the \(k\)-server problem. Zbl 0801.68122
Alon, Noga; Karp, Richard M.; Peleg, David; West, Douglas
2
1992
Three-stage generalized connectors. Zbl 0752.94022
Karp, Richard M.
1
1992
Competitive paging algorithms. Zbl 0753.68018
Fiat, Amos; Karp, Richard M.; Luby, Michael; McGeoch, Lyle A.; Sleator, Daniel D.; Young, Neal E.
59
1991
An introduction to randomized algorithms. Zbl 0757.68085
Karp, Richard M.
5
1991
Transitive compaction in parallel via branchings. Zbl 0718.68058
Gibbons, Phillip; Karp, Richard; Ramachandran, Vijaya; Soroker, Danny; Tarjan, Robert
3
1991
Parallel algorithms for shared-memory machines. Zbl 0900.68267
Karp, Richard M.; Ramachandran, Vijaya
179
1990
The transitive closure of a random digraph. Zbl 0712.68076
Karp, Richard M.
51
1990
Subtree isomorphism is in random NC. Zbl 0711.68052
Gibbons, Phillip B.; Karp, Richard M.; Miller, Gary L.; Soroker, Danny
1
1990
Monte-Carlo approximation algorithms for enumeration problems. Zbl 0678.65001
Karp, Richard M.; Luby, Michael; Madras, Neal
46
1989
The complexity of parallel search. Zbl 0651.68048
Karp, Richard M.; Upfal, Eli; Wigderson, Avi
19
1988
Deferred data structuring. Zbl 0662.68017
Karp, Richard M.; Motwani, Rajeev; Raghavan, Prabhakar
3
1988
Subtree isomorphism is in random NC. Zbl 0652.68078
Gibbons, Phillip B.; Miller, Gary L.; Karp, Richard M.; Soroker, Danny
1
1988
Efficient randomized pattern-matching algorithms. Zbl 0653.68054
Karp, Richard M.; Rabin, Michael O.
105
1987
Global wire routing in two-dimensional arrays. Zbl 0634.94024
Karp, 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.65054
Adler, Ilan; Karp, Richard M.; Shamir, Ron
10
1987
An upper bound on the expected cost of an optimal assignment. Zbl 0639.90066
Karp, Richard M.
5
1987
Constructing a perfect matching is in random NC. Zbl 0646.05051
Karp, R. M.; Upfal, E.; Wigderson, A.
55
1986
Probabilistic analysis of optimum partitioning. Zbl 0611.60011
Karmarkar, 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.90064
Adler, Ilan; Karp, Richard; Shamir, Ron
7
1986
Combinatorics, complexity, and randomness. Zbl 0642.68004
Karp, Richard M.
5
1986
A fast parallel algorithm for the maximal independent set problem. Zbl 0633.68026
Karp, Richard M.; Wigderson, Avi
46
1985
Monte-Carlo algorithms for the planar multiterminal network reliability problem. Zbl 0596.90033
Karp, Richard M.; Luby, Michael
35
1985
Probabilistic analysis of heuristics. Zbl 0582.90100
Karp, R. M.; Steele, J. M.
30
1985
Probabilistic analysis. Zbl 0588.90062
Karp, 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.68034
Karp, Richard M.; Pearl, Judea
15
1983
On the security of ping-pong protocols. Zbl 0514.94012
Dolev, 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.68025
Karp, Richard M.; Lipton, Richard J.
59
1982
Dynamic programming meets the principle of inclusion and exclusion. Zbl 0486.90083
Karp, Richard M.
32
1982
On linear characterizations of combinatorial optimization problems. Zbl 0505.65020
Karp, Richard M.; Papadimitriou, Christos H.
27
1982
On the security of ping-pong protocols. Zbl 0537.94012
Dolev, D.; Even, S.; Karp, R. M.
13
1982
Turing machines that take advice. Zbl 0494.68061
Karp, Richard M.; Lipton, Richard J.
7
1982
Parametric shortest path algorithms with an application to cyclic staffing. Zbl 0453.68032
Karp, Richard M.; Orlin, James B.
29
1981
The complexity of testing whether a graph is a superconcentrator. Zbl 0482.05059
Blum, 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.68076
Karp, Richard M.
8
1980
Linear expected-time algorithms for connectivity problems. Zbl 0463.68060
Karp, Richard M.; Tarjan, Robert Endre
7
1980
A patching algorithm for the nonsymmetric traveling-salesman problem. Zbl 0427.90064
Karp, Richard M.
49
1979
Probabilistic analysis of a canonical numbering algorithm for graphs. Zbl 0428.68052
Karp, Richard M.
3
1979
A characterization of the minimum cycle mean in a digraph. Zbl 0386.05032
Karp, Richard M.
173
1978
Probabilistic analysis of partitioning algorithms for the traveling- salesman problem in the plane. Zbl 0391.90090
Karp, R. M.
5
1978
Probabilistic analysis of partitioning algorithms for the traveling- salesman problem in the plane. Zbl 0391.90091
Karp, Richard M.
70
1977
The probabilistic analysis of some combinatorial search algorithms. Zbl 0368.68035
Karp, Richard M.
12
1976
Parallel program schemata. Zbl 0369.68013
Karp, R. M.; Miller, R. E.
9
1976
On the optimality of Huffman trees. Zbl 0349.05101
Glassey, C. R.; Karp, R. M.
8
1976
Reducibility among combinatorial problems. Zbl 0366.68041
Karp, R. M.
692
1975
...and 27 more Documents
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.