The Algorithms group at ICSI.
J. Elson, R.M. Karp, C.H. Papadimitriou and S. Shenker. Global Synchronization in Sensornets. Proceedings of LATIN, 609-624, 2004.
B. Godfrey, R.M. Karp, K. Lakshminarayanan, S. Surana and I. Stoica. Load Balancing in Dynamic Structured P2P Systems. Proceedings of INFOCOMM, 2004.
M. Adler, E. Halperin, R.M. Karp and V Vazirani. A Stochastic Process on the Hypercube with Applications to Peer-to-peer Networks. Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing (STOC 2003).
R.M. Karp, S. Shenker and C.H. Papadimitriou. A Simple Algorithm for Finding Frequent Elements in Streams and Bags. Transactions on Database Systems 28: 51-55, 2003.
A. Rao, K. Lakshminaryanan, S. Surana, R.M. Karp and I. Stoica. Load Balancing in Structured P2P Systems. Proceedings of the Second International Workshop on Peer-to-Peer Systems, 2003.
A. Akella, R.M. Karp, C. Papadimitriou, S. Seshan and S. Shenker. Selfish Behavior and Stability of the Internet: A Game-Theoretic Analysis of TCP. In Proceedings ACM SIGCOMM 2002.
S. Ratnasamy, M. Handley, R.M. Karp and S. Shenker. Topologically-Aware Overlay Construction and Server Selection. INFOCOM, 2002.
S. Ratnasamy, P. Francis, M. Handley, R.M. Karp and S. Shenker. A Scalable Content-Addressable Network. Proc. ACM SIGCOMM 2001.
S. Ratnasamy, M. Handley, R.M. Karp and S. Shenker. Application-level Multicast using Content-Addressable Networks. In Proceedings of 3rd International Workshop on Networked Group Communication, London, Nov 2001.
M. Adler, J. Byers and R.M. Karp. Parallel Sorting with Limited Bandwidth. SIAM Journal of Computing 29(6): 1997-2015, 2000.
R.M. Karp, E. Koutsoupias, C.H. Papadimitriou and S. Shenker. Optimization Problems in Congestion Control. FOCS 2000: 66-74.
R.M. Karp, C. Schindelhauer, S. Shenker and B. Vocking. Randomized Rumor Spreading. FOCS 2000, 565-574.
R.M. Karp and R. Shamir. Algorithms for Optical Mapping. Journal of Computational Biology 7(1,2) 2000.
T.E. Ideker, V. Thorsson and R.M. Karp. Discovery of Regulatory Interactions Through Perturbation: Inference and Experimental Design. Proceedings of Pacific Symposium on Biocomputing (2000).
A. Ben-Dor, R. Karp, B. Schwikowski and Z. Yakhini. Universal DNA Tag Systems: A Combinatorial Design Scheme. Proceedings of RECOMB 2000.
Dagum, P., Karp, R., Luby, M., Ross, S. An Optimal Algorithm for Monte Carlo Estimation. SIAM Journal on Computing, SIAM J. Comput. (USA), vol.29, (no.5), SIAM, 2000. p.1484-96.
Condon, A., Karp, R.M. Edited by: Hochbaum, D., Jansen, K., Rolim, J.D.P., Sinclair, A. Algorithms for graph partitioning on the planted partition model. (Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques. Third International Workshop on Radomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX'99. Proceedings (Lecture Notes in Computer Science Vol.1671), Berkeley, CA, USA, 8-11 Aug. 1999.) Berlin, Germany: Sprnger-Verlag, 1999. p.221-32. ix+287 pp. 14
Karp, R.M., Kenyon, C., Waarts, O. Error-resilient DNA computation. Random Structures & Algorithms, Random Struct. Algorithms (USA), vol.15, (no.3-4), Wiley, Oct.-Dec. 1999. p.450-66. 19
Condon, A.; Edelsbrunner, H.; Emerson, E.A.; Fortnow, L.; and others. Challenges for theory of computing. SIGACT News, June 1999, vol.30, (no.2):62-76.
Karp, R.M.; Yanjun Zhang. On parallel evaluation of game trees. Journal of the ACM, Nov. 1998, vol.45, (no.6):1050-75.
Tao Jiang; Karp, R.M. Mapping clones with a given ordering or interleaving. Algorithmica, July 1998, vol.21, (no.3):262-84.
Beame, P.; Karp, R.; Pitassi, T.; Saks, M. On the complexity of unsatisfiability proofs for random k-CNF formulas. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. May 1998. New York, NY, USA: ACM, 1998. p. 561-71.
Karp, R.M. Variations on the theme of "twenty questions". Proceedings. 1998 IEEE International Symposium on Information Theory, Aug. 1998. New York, NY, USA: IEEE, 1998. p. 3.
Fasulo, D.; Tao Jiang; Karp, R.M.; Sharma, N. Constructing maps using the span and inclusion relations. RECOMB 98. Proceedings of the Second Annual International Conference on Computational Molecular Biology. March 1998. Edited by: Istrail, S.; Pevzner, P.; Waterman, M. New York, NY, USA: ACM, 1998. p. 64-73.
Karp, R.M.; Shamir, R. Algorithms for optical mapping. RECOMB 98. Proceedings of the Second Annual International Conference on Computational Molecular Biology. 22-25 March 1998. Edited by: Istrail, S.; Pevzner, P.; Waterman, M. New York, NY, USA: ACM, 1998. p. 117-24.
Aho, A.V.; Johnson, D.S.; Karp, R.M.; Kosaraju, S.R.; and others. Emerging opportunities for theoretical computer science. SIGACT News, Sept. 1997, vol.28, (no.3):65-74.
Blomer, J.; Karp, R.; Welzl, E. The rank of sparse random matrices over finite fields. Random Structures & Algorithms, July 1997, vol.10, (no.4):407-19.
Tao Jiang; Karp, R.M. Mapping clones with a given ordering or interleaving. Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Jan. 1997. New York, NY, USA: ACM, 1997. p. 400-9.
Zamir, O.; Etzioni, O.; Madani, O.; Karp, R.M. Fast and intuitive clustering of Web documents. Proceedings of the Third International Conference on Knowledge Discovery and Data Mining. 14-17 Aug. 1997. Edited by: Heckerman, D.; Mannila, H.; Pregibon, D.; Uthurusamy, R. Menlo Park, CA, USA: AAAI Press, 1997. p. 287-90.
Karp, R.M.; Luby, M.; Meyer auf der Heide, F. Efficient PRAM simulation on a distributed memory machine. Algorithmica, Oct.-Nov. 1996, vol.16, (no.4-5):517-42.
Alt, H.; Guibas, L.; Mehlhorn, K.; Karp, R.; and others. A method for obtaining randomized algorithms with small tail probabilities. Algorithmica, Oct.-Nov. 1996, vol.16, (no.4-5):543-7.
Gusfield, D.; Karp, R.; Lusheng Wang; Stelling, P. Graph traversals, genes, and matroids: an efficient case of the travelling salesman problem. Combinatorial Pattern Matching. 7th Annual Symposium, CPM 96. Proceedings. 10-12 June 1996. Berlin, Germany: Springer-Verlag, 1996. p. 304-19.
Etzioni, O.; Hanks, S.; Jiang, T.; Karp, R.M.; and others. Efficient information gathering on the Internet. Proceedings. 37th Annual Symposium Foundations of Computer Science, 14-16 Oct. 1996. Los Alamitos, CA, USA: IEEE Comput. Soc. Press, 1996. p. 234-43.
Frieze, A.; Karp, R.M.; Reed, B. When is the assignment bound tight for the asymmetric traveling-salesman problem?. SIAM Journal on Computing, June 1995, vol.24, (no.3):484-93.
Alon, N.; Karp, R.M.; Peleg, D.; West, D. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, Feb. 1995, vol.24, (no.1):78-100.
Adler, M.; Byers, J.W.; Karp, R.M. Scheduling parallel communication: the h-relation problem. Mathematical Foundations of Computer Science 1995. 20th International Symposium, MFCS '95. Proceedings. Aug.-1 Sept. 1995. Edited by: Wiedermann, J.; Hajek, P. Berlin, Germany: Springer-Verlag, 1995. p. 1-20.
Dagum, P.; Karp, R.; Luby, M.; Ross, S. An optimal algorithm for Monte Carlo estimation. Proceedings. 36th Annual Symposium on Foundations of Computer Science, 23-25 Oct. 1995. Los Alamitos, CA, USA: IEEE Comput. Soc. Press, 1995. p. 142-9.
Karp, R.M.; Waarts, O.; Zweig, G. The bit vector intersection problem. Proceedings. 36th Annual Symposium on Foundations of Computer Science, 23-25 Oct. 1995. Los Alamitos, CA, USA: IEEE Comput. Soc. Press, 1995. p. 621-30.
Karp, R.M. Modeling parallel communication. Proceedings 9th International Parallel Processing Symposium, 25-28 April 1995. Los Alamitos, CA, USA: IEEE Comput. Soc. Press, 1995. p. 2.
Adler, M.; Byers, J.W.; Karp, R.M. Parallel sorting with limited bandwidth. SPAA '95. 7th Annual ACM Symposium on Parallel Algorithms and Architectures. 17-19 July 1995. New York, NY, USA: ACM, 1995. p. 129-36.
Karp, R.M. Probabilistic recurrence relations. Journal of the Association for Computing Machinery, J. Assoc. Comput. Mach. (USA), vol.41, (no.6), Nov. 1994. p.1136-50.
Hellerstein, L., Gibson, G.A., Karp, R.M., Katz, R.M., Patterson, D.A. Coding techniques for handling failures in large disk arrays. Algorithmica, Algorithmica (Germany), vol.12, (no.2-3), Aug.-Sept. 1994. p.182-208.
Karp, R.M., Rinnooy Kan, A.H.G., Vohra, R.V. Average case analysis of a heuristic for the assignment problem. Mathematics of Operations Research, Math. Oper. Res. (USA), vol.19, (no.3), Aug. 1994. p.513-22.
Ronen, B., Karp, R. An information entropy approach to the small-lot concept. IEEE Transactions on Engineering Management, IEEE Trans. Eng. Manage. (USA), vol.41, (no.1), Feb. 1994. p.89-92. 9
Ben-David, S., Borodin, A., Karp, R., Tardos, G., Wigderson, A. On the power of randomization in on-line algorithms. Algorithmica, Algorithmica (Germany), vol.11, (no.1), Jan. 1994. p.2-14.
Alizadeh, F., Karp, R.M., Weisser, D.K., Zweig, G. Physical mapping of chromosomes using unique probes. (Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, USA, 23-25 Jan. 1994.) New York, NY, USA: ACM, 1994. p.489-500. 734 pp.
Adler, M., Gemmell, P., Harchol-Balter, M., Karp, R.M., Kenyon, C. Selection in the presence of noise: the design of playoff systems. (Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, USA, 23-25 Jan. 1994.) New York, NY, USA: ACM, 1994. p.564-72. 734 pp.
Karp, R.M., Zhang, Y. Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the Association for Computing Machinery, J. Assoc. Comput. Mach. (USA), vol.40, (no.3), July 1993. p.765-89.
Culler, D., Karp, R., Patterson, D., Sahay, A., Schauser, K.E., Santos, E., Subramonian, R., von Eicken, T. LogP: towards a realistic model of parallel computation. SIGPLAN Notices, SIGPLAN Not. (USA), vol.28, (no.7), (Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, CA, USA, 19-22 May 1993.) July 1993. p.1-12.
Karmarkar, N., Karp, R., Lipton, R., Lovasz, L., Luby, M. A Monte-Carlo algorithm for estimating the permanent. SIAM Journal on Computing, SIAM J. Comput. (USA), vol.22, (no.2), April 1993. p.284-93.
Karp, R.M., Motwani, R., Nisan, N. Probabilistic analysis of network flow algorithms. Mathematics of Operations Research, Math. Oper. Res. (USA), vol.18, (no.1), Feb. 1993. p.71-97.
Karp, R.M. Edited by: Dehne, F., Sack, J.R., Santoro, N., Whitesides, S. A generalization of binary search. (Algorithms and Data Structures. Third Workshop, WADS'93, Montreal, Que., Canada, 11-13 Aug. 1993.) Berlin, Germany: Springer-Verlag, 1993. p.27-34. xii+633 pp.
Karp, R.M. Mapping the Genome: some combinatorial problems arising in molecular biology. (Proceedings of 25th Annual Symposium on the Theory of Computing, San Diego, CA, USA, 16-18 May 1993.) New York, NY, USA: ACM, 1993. p.278-85. ix+812 pp.
El-Yaniv, R., Karp, R.M. The mortgage problem. (Proceedings of the 2nd Israel Symposium on Theory and Computing Systems (Cat. No.93TH0520-7), Natanya, Israel, 7-9 June 1993.) Los Alamitos, CA, USA: IEEE, 1993. p.304-12. x+313 pp.
Karp, R.M. On-line algorithms versus off-line algorithms: how much is it worth to know the future?. IFIP Transactions A (Computer Science and Technology), IFIP Trans. A, Comput. Sci. Technol. (Netherlands), vol.A-12, (Algorithms, Software, Architecture. Information Processing 92. IFIP 12th World Computer Congress, Madrid, Spain, 7-11 Sept. 1992.) 1992. p.416-29.
Karp, R.M., Luby, M., Meyer auf der Heide, F. Efficient PRAM simulation on a distributed memory machine. (Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, Victoria, BC, Canada, 4-6 May 1992.) New York, NY, USA: ACM, 1992. p.318-26. ix+784 pp. 14
El-Yaniv, R., Fiat, A., Karp, R., Turpin, G. Competitive analysis of financial games. (Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), Pittsburgh, PA, USA, 24-27 Oct. 1992.) Los Alamitos, CA, USA: IEEE Comput. Soc. Press, 1992. p.327-33. xi+734 pp.
Fiat, A., Karp, R.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E. Competitive paging algorithms. Journal of Algorithms, J. Algorithms (USA), vol.12, (no.4), Dec. 1991. p.685-99.
Karp, R.M. An introduction to randomized algorithms. Discrete Applied Mathematics, Discrete Appl. Math. (Netherlands), vol.34, (no.1-3), (Capital City Conference on Combinatorics and Theoretical Computer Science, Washington, DC, USA, 22-26 May 1989.) 21 Nov. 1991. p.165-201.
Gibbons, P., Karp, R., Ramachandran, V., Soroker, D., Tarjan, R. Transitive compaction in parallel via branchings. Journal of Algorithms, J. Algorithms (USA), vol.12, (no.1), March 1991. p.110-25.
Floyd, S., Karp, R.M. FFD bin packing for item sizes with uniform distributions on (0, 1/2). Algorithmica, Algorithmica (Germany), vol.6, (no.2), 1991. p.222-40.
Gibbons, P.B., Karp, R.M., Miller, G.L., Soroker, D. Subtree isomorphism is in random NC. Discrete Applied Mathematics, Discrete Appl. Math. (Netherlands), vol.29, (no.1), Nov. 1990. p.35-62.
Karp, R.M., Vazirani, U.V., Vazirani, V.V. An optimal algorithm for on-line bipartite matching. (Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, 14-16 May 1990.) New York, NY, USA: ACM, 1990. p.352-8. viii+574 pp.
Ben-David, S., Borodin, A., Karp, R., Tardos, G., Wigderson, A. On the power of randomization in online algorithms. (Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, 14-16 May 1990.) New York, NY, USA: ACM, 1990. p.379-86. viii+574 pp.
Karp, R.M., Luby, M., Madras, N. Monte-Carlo approximation algorithms for enumeration problems. Journal of Algorithms, J. Algorithms (USA), vol.10, (no.3), Sept. 1989. p.429-48.
Gibson, G.A., Hellerstein, L., Karp, R.M., Katz, R.H., Patterson, D.A. Failure correction techniques for large disk arrays. (ASPLOS-III Proceedings. Third International Conference on Architectural Support for Programming Languages and Operating Systems, Boston, MA, USA, 3-6 April 1989.) New York, NY, USA: ACM, 1989. p.123-32. x+303 pp.
Karp, R.M., Yanjun Zhang On parallel evaluation of game trees. (SPAA '89. Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures, Santa Fe, NM, USA, 19-21 June 1989.) New York, NY, USA: ACM, 1989. p.409-20. x+433 pp.
Karp, R.M., Motwani, R., Raghavan, P. Deferred data structuring. SIAM Journal on Computing, SIAM J. Comput. (USA), vol.17, (no.5), Oct. 1988. p.883-902.
Karp, R.M., Upfal, E., Wigderson, A. The complexity of parallel search. Journal of Computer and System Sciences, J. Comput. Syst. Sci. (USA), vol.36, (no.2), (17th Annual ACM Symposium on the Theory of Computing, Providence, RI, USA, 6-8 May 1985.) April 1988. p.225-53.
Karp, R.M., Zhang, Y. A randomized parallel branch-and-bound procedure. (Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, 2-4 May 1988.) New York, NY, USA: ACM, 1988. p.290-300. viii+553 pp.
Gibbons, P.B., Karp, R.M., Miller, G.L., Soroker, D. Edited by: Reif, J.H. Subtree isomorphism is in random NC. (VLSI Algorithms and Architectures. 3rd Aegean Workshop on Computing, AWOC 88. Proceedings, Corfu, Greece, 28 June-1 July 1988.) Berlin, West Germany: Springer-Verlag, 1988. p.43-52. x+476 pp.
Adler, I., Karp, R.M., Shamir, R. A Simplex variant solving an m*d linear program in O(min(m/sup 2/, d/sup 2/)) expected number of pivot steps. Journal of Complexity, J. Complexity (USA), vol.3, (no.4), Dec. 1987. p.372-87.
Karp, R.M., Rabin, M.O. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, IBM J. Res. Dev. (USA), vol.31, (no.2), March 1987. p.249-60.
Karp, R.M., Leighton, F.T., Rivest, R.L., Thompson, C.D., Vazirani, U.V., Vazirani, V.V. Global wire routing in two-dimensional arrays. Algorithmica, Algorithmica (West Germany), vol.2, (no.1), 1987. p.113-29.
Adler, I., Karp, R., Shamir, R. A family of simplex variants solving an m*d linear program in expected number of pivot steps depending on d only. Mathematics of Operations Research, Math. Oper. Res. (USA), vol.11, (no.4), Nov. 1986. p.570-90.
Karp, R.M. Combinatorics, complexity and stochastic algorithms. Informatie, Informatie (Netherlands), vol.28, (no.9), Sept. 1986. p.722-33.
Karp, R.M. Combinatorics, complexity, and randomness. Communications of the ACM, Commun. ACM (USA), vol.29, (no.2), Feb. 1986. p.98-109.
Karp, R.M. Edited by: Leiserson, C.E. The complexity of parallel computation. (Advanced Research in VLSI. Proceedings of the Fourth MIT Conference, Cambridge, MA, USA, 7-9 April 1986.) Cambridge, MA, USA: MIT Press, 1986. p.197. x+118 pp.
Frankle, J., Karp, R.M. Circuit placements and costs bounds by eigenvector decomposition. (IEEE International Conference on Computer-Aided Design: ICCAD-86. A Conference for the EE CAD Professional. Digest of Technical Papers (Cat. No.86CH2353-1), Santa Clara, CA, USA, 11-13 Nov. 1986.) Washington, DC, USA: IEEE Comput. Soc. Press, 1986. p.414-17. xxxii+523 pp.
Karp, R.M., Saks, M., Wigderson, A. On a search problem related to branch-and-bound procedures. (27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), Toronto, Ont., Canada, 27-29 Oct. 1986.) Washington, DC, USA: IEEE Comput. Soc. Press, 1986. p.19-28. xiv+517 pp.
Floyd, S., Karp, R. FED bin packing for item sizes with distributions on (0,1/2). (27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), Toronto, Ont., Canada, 27-29 Oct. 1986.) Washington, DC, USA: IEEE Comput. Soc. Press, 1986. p.322-30. xiv+517 pp.
Karp, R.M., Luby, M. Monte-Carlo algorithms for the planar multiterminal network reliability problem. Journal of Complexity, J. Complexity (USA), vol.1, (no.1), (Symposium on the Complexity of Approximately Solved Problems, New York, NY, USA, 17-19 April 1985.) Oct. 1985. p.45-64.
Karp, R.M., Wigderson, A. A fast parallel algorithm for the maximal independent set problem. Journal of the Association for Computing Machinery, J. Assoc. Comput. Mach. (USA), vol.32, (no.4), Oct. 1985. p.762-73.
Karp, R.M. The complexity of parallel computation. (Proceedings of the Twenty-third Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, 2-4 Oct. 1985.) Urbana-Champaign, IL, USA: Univ. Illinois, 1985. p.1. xvii+1000 pp.
Karp, R.M., Pearl, J. Searching for an optimal path in a tree with random costs. Artificial Intelligence, Artif. Intell. (Netherlands), vol.21, (no.1-2), March 1983. p.99-916.
Dolev, D., Even, S., Karp, R.M. Edited by: Chaum, D., Rivest, R.L., Sherman, A.T. On the security of ping-pong protocols. (Advances in Cryptology, Proceedings of Crypto 82, Santa Barbara, CA, USA, 23-25 Aug. 1982.) New York, NY, USA: Plenum, 1983. p.177-86. xv+331 pp.
Karp, R.M., Luby, M. Monte-Carlo algorithms for enumeration and reliability problems. (24th Annual Symposium on Foundations of Computer Science, Tucson, AZ, USA, 7-9 Nov. 1983.) Silver Spring, MD, USA: IEEE Comput. Soc. Press, 1983. p.56-64. xii+477 pp.
Karp, R.M., Leighton, F.T., Rivest, R.L., Thompson, C.D., Vazirani, U., Vazirani, V. Global wire routing in two-dimensional arrays. (24th Annual Symposium on Foundations of Computer Science, Tucson, AZ, USA, 7-9 Nov. 1983.) Silver Spring, MD, USA: IEEE Comput. Soc. Press, 1983. p.453-9. xii+477 pp.
Karp, R.M., Papadimitriou, C.H. On linear characterizations of combinatorial optimization problems. SIAM Journal on Computing, SIAM J. Comput. (USA), vol.11, (no.4), Nov. 1982. p.620-32.
Dolev, D., Even, S., Karp, R.M. On the security of ping-pong protocols. Information and Control, Inf. Control (USA), vol.55, (no.1-3), Oct.-Dec. 1982. p.57-68.
Karp, R.M. Dynamic programming meets the principle of inclusion and exclusion. Operations Research Letters, Oper. Res. Lett. (Netherlands), vol.1, (no.2), April 1982. p.49-51.
Karmarkar, N., Karp, R.M. An efficient approximation scheme for the one-dimensional bin-packing problem. (23rd Annual Symposium on Foundations of Computer Science, Chicago, IL, USA, 3-5 Nov. 1982.) New York, NY, USA: IEEE, 1982. p.312-20. vii+385 pp.
Karp, R.M., Orlin, J.B. Parametric shortest path algorithms with an application to cyclic staffing. Discrete Applied Mathematics (Netherlands), vol.3, (no.1), Feb. 1981. p.37-45.
Blum, M., Karp, R.M., Vornberger, O., Papadimitriou, C.H., Yannakakis, M. The complexity of testing whether a graph is a superconcentrator. Information Processing Letters, Inf. Process. Lett. (Netherlands), vol.13, (no.4-5), 1981. p.164-7.
Karp, R.M., Sipser, M. Maximum matchings in sparse random graphs. (22nd Annual Symposium on Foundations of Computer Science, Nashville, TN, USA, 28-30 Oct. 1981.) New York, NY, USA: IEEE, 1981. p.364-75. ix+429 pp.
Karp, R.M. An algorithm to solve the m*n assignment problem in expected time O(mn log n)*. Networks, Networks (USA), vol.10, (no.2), Summer 1980. p.143-52.
Karp, R.M., Papadimitriou, C.H. On linear characterizations of combinatorial optimization problems. (21st Annual Symposium on Foundations of Computer Science, Syracuse, NY, USA, 13-15 Oct. 1980.) New York, NY, USA: IEEE, 1980. p.1-9. vi+421 pp.
Karp, R.M. A patching algorithm for the nonsymmetric traveling-salesman problem. SIAM Journal on Computing, SIAM J. Comput. (USA), vol.8, (no.4), Nov. 1979. p.561-73.
Karp, R.M. Edited by: Maurer, H.A. Recent advances in the probabilistic analysis of graph-theoretic algorithms. (Automata, Languages and Programming, Graz, Austria, 16-20 July 1979.) Berlin, West Germany: Springer-Verlag, 1979. p.338-9. ix+684 pp.
Karp, R.M. Probabilistic analysis of graph-theoretic algorithms. (Proceedings of the Computer Science and Statistics 12th Annual Symposium on the Interface, Waterloo, Ont., Canada, 10-11 May 1979.) Waterloo, Ont., Canada: Univ. Waterloo, 1979. p.173. xiii+500 pp.
Aleliunas, R., Karp, R.M., Lipton, R.J., Lovasz, L. Random walks, universal traversal sequences, and the complexity of maze problems. (Proceedings of the Computer Science and Statistics 12th Annual Symposium on the Interface, Waterloo, Ont., Canada, 10-11 May 1979.) Waterloo, Ont., Canada: Univ. Waterloo, 1979. p.174-6. xiii+500 pp.
Aleliunas, R., Karp, R.M., Lipton, R.J., Lovasz, L., Rackoff, C. Random walks, universal traversal sequences, and the complexity of maze problems. (20th Annual Symposium of Foundations of Computer Science, San Juan, Puerto Rico, 29-31 Oct. 1979.) New York, NY, USA: IEEE, 1979. p.218-23. vii+431 pp.
Karp, R.M. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, Discrete Math. (Netherlands), vol.23, (no.3), Sept. 1978. p.309-11.
Karp, R.M. Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Mathematics of Operations Research, Math. Oper. Res. (USA), vol.2, (no.3), Aug. 1977. p.209-24.
Glassey, C.R., Karp, R.M. On the optimality of Huffman trees. SIAM Journal on Applied Mathematics, SIAM J. Appl. Math. (USA), vol.31, (no.2), Sept. 1976. p.368-78.
Karp, R.M., Li, S.-Y.R. Two special cases of the assignment problem. Discrete Mathematics, Discrete Math. (Netherlands), vol.13, (no.2), Oct. 1975. p.129-42.
Karp, R., Matula, D.W. Probabilistic behavior of a naive coloring algorithm on random graphs. Bulletin of the Operations Research Society of America, Bull. Oper. Res. Soc. Am. (USA), vol.23, suppl.2, (ORSA/TIMS National Meeting. (Abstracts only), Las Vegas, NV, USA, 17-19 Nov. 1975.) Fall 1975. p.B264.
Karp, R.M., McKellar, A.C., Wong, C.K. Near-optimal solutions to a 2-dimensional placement problem. SIAM Journal on Computing, SIAM J. Comput. (USA), vol.4, (no.3), Sept. 1975. p.271-86.
Karp, R.M. On the computational complexity of combinatorial problems. Networks, Networks (USA), vol.5, (no.1), (Proceedings of the Symposium on Large-Scale Networks, Evanston, IL, USA, 18-19 April 1974.) Jan. 1975. p.45-68.
Glassey, C.R., Karp, R.M. On the optimality of Huffman trees. Univ. California, Berkeley, CA, USA, July 1974. 26 pp. Report number: ORC-74-21
Hopcroft, J.E., Karp, R.M. An n/sup 5/2/ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, SIAM J. Comput. (USA), vol.2, (no.4), Dec. 1973. p.225-31.
Gale, D., Karp, R.M. A phenomenon in the theory of sorting. Journal of Computer and System Sciences, J. Comput. Syst. Sci. (USA), vol.6, (no.2), April 1972. p.103-15.
Edmonds, J., Karp, R.M. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the Association for Computing Machinery, J. Assoc. Comput. Mach. (USA), vol.19, (no.2), April 1972. p.248-64. 7
Karp, H.R. Digital-to-analog converters: trading off bits and bucks. Electronics, Electronics (USA), vol.45, (no.6), 13 March 1972. p.84-90.