Publications

Found 238 results
Author Title Type [ Year(Asc)]
Filters: Author is Richard M. Karp  [Clear All Filters]
1986
Adler, I., Karp R. M., & Shamir R. (1986).  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. 11(4), 570-590.
Floyd, S., & Karp R. M. (1986).  FED bin packing for item sizes with distributions on (0,1/2). Proceedings of the 27th Annual Symposium on Foundations of Computer Science. 322-330.
Karp, R. M., Saks M., & Wigderson A. (1986).  On a Search Problem Related to Branch-and-Bound Procedures. Proceedings of the 27th Annual Symposium on Foundations of Computer Science. 19-28.
1985
Karp, R. M. (1985).  The complexity of parallel computation. Proceedings of the 23rd Annual Allerton Conference on Communication, Control, and Computing. 1.
Karp, R. M., & Wigderson A. (1985).  A fast parallel algorithm for the maximal independent set problem. Journal of the Association for Computing Machinery. 32(4), 762-773.
Karp, R. M., & Luby M. (1985).  Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem. Journal of Complexity. 1,
Karp, R. M., & Luby M. (1985).  Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem. Proceedings of the Symposium on the Complexity of Approximately Solved Problems. 45-64.
1983
Karp, R. M., F. Leighton T., Rivest R. L., Thomborson C. David, Vazirani U. V., & Vazirani V. V. (1983).  Global Wire Routing in Two-Dimensional Arrays. Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 453-459.
Karp, R. M., & Luby M. (1983).  Monte-Carlo Algorithms for Enumeration and Reliability Problems. Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 56-64.
Karp, R. M., & Pearl J.. (1983).  Searching for an optimal path in a tree with random costs. Artificial Intelligence. 21(1-2), 99-116.
1982
Karp, R. M. (1982).  Dynamic Programming Meets the Principle of Inclusion and Exclusion. Operations Research Letters. 1(2), 49-51.
Karmarkar, N., & Karp R. M. (1982).  An efficient approximation scheme for the one-dimensional bin-packing problem. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. 312-320.
Karp, R. M., & Papadimitriou C. H. (1982).  On Linear Characterizations of Combinatorial Optimization Problems. SIAM Journal on Computing. 11(4), 620-632.
Dolev, D., Even S., & Karp R. M. (1982).  On the security of ping-pong protocols.
Dolev, D., Even S., & Karp R. M. (1982).  On the security of ping-pong protocols. 55(1-3), 57-68.
1981
Blum, M. E., Karp R. M., Vornberger O.., Papadimitriou C. H., & Yannakakis M.. (1981).  The Complexity of Testing Whether a Graph is a Superconcentrator. 13(4-5), 164-167.
Karp, R. M., & Sipser M.. (1981).  Maximum Matchings in Sparse Random Graphs. Proceedings of the 22nd IEEE Annual Symposium on Foundations of Computer Science. 364-375.
Karp, R. M., & Orlin J.. B. (1981).  Parametric Shortest Path Algorithms with an Application to Cyclic Staffing. Discrete Applied Mathematics (Netherlands). 3(1), 37-45.
1980
Karp, R. M. (1980).  An Algorithm to Solve the m*n Assignment Problem in Expected Time O(mn log n)*. 10(2), 143-152.
Karp, R. M., & Papadimitriou C. H. (1980).  On Linear Characterizations of Combinatorial Optimization Problems. Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. 1-9.
1979
Karp, R. M. (1979).  A Patching Algorithm for the Nonsymmetric Traveling-salesman Problem. SIAM Journal on Computing. 8(4), 561-573.
Karp, R. M. (1979).  Probabilistic Analysis of Graph-theoretic Algorithms. Proceedings of the Computer Science and Statistics 12th Annual Symposium on the Interface.
Aleliunas, R., Karp R. M., Lipton R. J., & Lovász L. (1979).  Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. Proceedings of the Computer Science and Statistics 12th Annual Symposium on the Interface. 174-176.
Aleliunas, R., Karp R. M., Lipton R. J., Lovász L., & Rackoff C. (1979).  Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. Proceedings of the 20th Annual IEEE Symposium of Foundations of Computer Science. 218-223.
Karp, R. M. (1979).  Recent Advances in the Probabilistic Analysis of Graph-theoretic Algorithms. 338-339.

Pages