# Journal of the ACM Bibliography

Rajeev Motwani. Average-case
analysis of algorithms for matchings and related problems. Journal
of the ACM, 41(6):1329-1356, November 1994.
[BibTeX entry]
**Selected references**

- B. Bollobás, T. I. Fenner, and A. M. Frieze. An algorithm for finding
Hamilton cycles in a random graph. In Proceedings of the
Seventeenth Annual ACM Symposium on Theory of Computing, pages
430-439, Providence, Rhode Island, 6-8 May 1985.

- Andrei Z. Broder. How hard is to marry at
random? (On the approximation of the permanent). In
Proceedings of the Eighteenth Annual ACM Symposium on Theory of
Computing, pages 50-58, Berkeley, California, 28-30 May 1986.

- S. Even and O. Kariv. An
`O`(`n`^{2.5}) algorithm for maximum matching in
general graphs. In 16th Annual Symposium on Foundations of
Computer Science, pages 100-112, The University of California,
Berkeley, 13-15 October 1975. IEEE.

- Tomás Feder and Rajeev Motwani. Clique partitions, graph
compression, and speeding-up algorithms. In Proceedings of the
Twenty Third Annual ACM Symposium on Theory of Computing, pages
123-133, New Orleans, Louisiana, 6-8 May 1991.

- Harold N. Gabow and Robert E. Tarjan. Almost-optimum speed-ups of
algorithms for bipartite matching and related problems. In
Proceedings of the Twentieth Annual ACM Symposium on Theory of
Computing, pages 514-527, Chicago, Illinois, 2-4 May 1988.

- Mark Jerrum and Alistair Sinclair. Conductance and the rapid
mixing property for Markov chains: the approximation of the permanent
resolved (preliminary version). In Proceedings of the
Twentieth Annual ACM Symposium on Theory of Computing, pages
235-244, Chicago, Illinois, 2-4 May 1988.

- Richard M. Karp and Michael Sipser. Maximum matchings in sparse
random graphs. In 22nd Annual Symposium on Foundations of
Computer Science, pages 364-375, Nashville, Tennessee, 28-30
October 1981. IEEE.

- Silvio Micali and Vijay V. Vazirani. An
`O`(\sqrt{|`v`|} \cdot |`E`|) algorithm for
finding maximum matching in general graphs. In 21st Annual
Symposium on Foundations of Computer Science, pages 17-27,
Syracuse, New York, 13-15 October 1980. IEEE.

### Shortcuts: