Publications
(1975).
A fast parallel algorithm for the maximal independent set problem.
Journal of the Association for Computing Machinery. 32(4), 762-773.
(1985). The complexity of parallel computation.
Proceedings of the 23rd Annual Allerton Conference on Communication, Control, and Computing. 1.
(1985). Searching for an optimal path in a tree with random costs.
Artificial Intelligence. 21(1-2), 99-116.
(1983). Monte-Carlo Algorithms for Enumeration and Reliability Problems.
Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 56-64.
(1983). Global Wire Routing in Two-Dimensional Arrays.
Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 453-459.
(1983). On Linear Characterizations of Combinatorial Optimization Problems.
SIAM Journal on Computing. 11(4), 620-632.
(1982). Dynamic Programming Meets the Principle of Inclusion and Exclusion.
Operations Research Letters. 1(2), 49-51.
(1982). Parametric Shortest Path Algorithms with an Application to Cyclic Staffing.
Discrete Applied Mathematics (Netherlands). 3(1), 37-45.
(1981). Maximum Matchings in Sparse Random Graphs.
Proceedings of the 22nd IEEE Annual Symposium on Foundations of Computer Science. 364-375.
(1981).
(1980). On Linear Characterizations of Combinatorial Optimization Problems.
Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. 1-9.
(1980). A Patching Algorithm for the Nonsymmetric Traveling-salesman Problem.
SIAM Journal on Computing. 8(4), 561-573.
(1979).
(1979). Probabilistic Analysis of Graph-theoretic Algorithms.
Proceedings of the Computer Science and Statistics 12th Annual Symposium on the Interface.
(1979). A Characterization of the Minimum Cycle Mean in a Digraph.
Discrete Mathematics (Netherlands). 23(3), 309-311.
(1978). Probabilistic Analysis of Partitioning Algorithms for the Traveling-salesman Problem in the Plane.
Mathematics of Operations Research. 2(3), 209-224.
(1977). On the Optimality of Huffman Trees.
SIAM Journal on Applied Mathematics. 31(2), 368-378.
(1976). Probabilistic Behavior of a Naive Coloring Algorithm on Random Graphs.
Bulletin of the Operations Research Society of America. 23,
(1975).
(1974). Near-optimal Solutions to a 2-dimensional Placement Problem.
SIAM Journal on Computing. 4(3), 271-286.
(1975). Two Special Cases of the Assignment Problem.
Discrete Mathematics (Netherlands). 13(2), 129-142.
(1975).
(1974).
(1975). An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs.
SIAM Journal on Computing. 2(4), 225-231.
(1973).