Publications
An optimal algorithm for on-line bipartite matching.
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing.
(1990). A fast parallel algorithm for the maximal independent set problem.
Journal of the Association for Computing Machinery. 32(4), 762-773.
(1985).
(1989). Modeling parallel communication.
Proceedings of the 9th International Parallel Processing Symposium (IPDPS '95). 2.
(1995). Monte-Carlo Algorithms for Enumeration and Reliability Problems.
Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 56-64.
(1983). Heuristic Algorithms in Computations Molecular Biology.
Journal of Computer and System Sciences. 77(1), 122-128.
(2011).
(1991). Global wire routing in two-dimensional arrays.
2(1), 113-129.
(1987). Probabilistic recurrence relations.
Journal of the Association for Computing Machinery. 41(6), 1136-1150.
(1994). On Linear Characterizations of Combinatorial Optimization Problems.
Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science. 1-9.
(1980). On the Optimality of Huffman Trees.
SIAM Journal on Applied Mathematics. 31(2), 368-378.
(1976).
(1993).
(2000). On a Search Problem Related to Branch-and-Bound Procedures.
Proceedings of the 27th Annual Symposium on Foundations of Computer Science. 19-28.
(1986).
(2011).
(2009). Searching for an optimal path in a tree with random costs.
Artificial Intelligence. 21(1-2), 99-116.
(1983). A randomized parallel branch-and-bound procedure.
Proceedings of the 20th Annual ACM Symposium on Theory of Computing. 290-300.
(1988). Dynamic Programming Meets the Principle of Inclusion and Exclusion.
Operations Research Letters. 1(2), 49-51.
(1982).
(2010). Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem.
Proceedings of the Symposium on the Complexity of Approximately Solved Problems. 45-64.
(1985). The Complexity of Parallel Search.
Proceedings of the 17th Annual ACM Symposium on the Theory of Computing. 225-253.
(1988). Efficient PRAM Simulation on a Distributed Memory Machine.
Algorithmica. 16(4-5), 517-542.
(1996). Mathematical Challenges from Genomics and Molecular Biology.
49(5), 544-553.
(2002). A generalization of binary search.
Proceedings of the Third Workshop on Algorithms and Data Structures (WADS'93). 27-34.
(1993).