Publications

Found 238 results
Author Title Type [ Year(Desc)]
Filters: Author is Richard M. Karp  [Clear All Filters]
1972
Gale, D.., & Karp R. M. (1972).  A Phenomenon in the Theory of Sorting. Journal of Computer and System Sciences. 6(2), 103-115.
Edmonds, J., & Karp R. M. (1972).  Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Journal of the Association for Computing Machinery. 19(2), 248-264.
1973
Karp, R. M., & Hopcroft J.. E. (1973).  An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal on Computing. 2(4), 225-231.
1976
Karp, R. M., & Glassey C.. R. (1976).  On the Optimality of Huffman Trees. SIAM Journal on Applied Mathematics. 31(2), 368-378.
1978
Karp, R. M. (1978).  A Characterization of the Minimum Cycle Mean in a Digraph. Discrete Mathematics (Netherlands). 23(3), 309-311.
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.
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.
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.
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.

Pages