Recent advances in the probabilistic analysis of graph-theoretic algorithms

1. Angluin, D. and L.G. Valiant, Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings. Proc. Ninth ACM Symposium on Theory of Computing (1977)

   Google Scholar 

2. Apers, P., The Expected Number of Phases of the Dinic-Karzanov Network Flow Algorithm. Informatica Rapport IR 27. Vrije Universiteit, Amsterdam (1978)

   Google Scholar 

3. Chvátal, V., Determining the Stability Number of a Graph. SIAM J. Comp 6 (1977) 643–662.

   Google Scholar 

4. Erdös, P. and A. Rényi., On Random Graphs I, Publicationes Mathematicae 6 (1959) 290–297.

   Google Scholar 

5. Erdös, P. and A. Rényi, On the Evolution of Random Graphs, Publ. Math. Inst. Hung. Acad. Sci. 5A (1960), 17–61.

   Google Scholar 

6. Erdös, P. and A. Rényi, On Random Matrices, Publ. Math. Inst. Hung. Acad. Sci., 8A (1963), 455–461.

   Google Scholar 

7. Erdös, P. and A. Rényi, On the Existence of a Factor of Degree One of a Connected Random Graph, Acta Math. Acad. Sci. Hung. 17 (1966), 359–368.

   Google Scholar 

8. Grimmett, G. R. and C. J. H. McDiarmid, On Coloring Random Graphs, Math. Proc. Camb. Phil. Soc. 77 (1975), 313–324.

   Google Scholar 

9. Hamacher, H., Numerical Investigations on the Maximal Flow Algorithm of Karzanov. Report 78-7, Mathematisches Institut, Universität zu Köln, (1978)

   Google Scholar 

10. Karp, R. M., The Probabilistic Analysis of Some Combinatorial Search Algorithms. Algorithms and Complexity: New Directions and Recent Results (Ed. J. Traub), Academic Press (1976).

    Google Scholar 

11. Karp, R. M., A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem. To appear in SIAM J. Comp. (1979).

    Google Scholar 

12. Karp, R. M. Probabilistic Analysis of a Canonical Numbering Algorithm for Graphs. Proc. AMS Symposia in Applied Mathematics 34 (1979).

    Google Scholar 

13. Karp, R. M., An Algorithm to Solve the m x n Assignment Problem in Expected Time O (mn log n), Memorandum No. UCB/ERL M78/67, Electronics Research Laboratory, University of California, Berkeley (1978)

    Google Scholar 

14. Lueker, G. S., Maximization Problems on Graphs with Edge Weights Chosen From a Normal Distribution. Proc. Tenth ACM Symposium on Theory of Computing (1978)

    Google Scholar 

15. McDiarmid, C., Determining the Chromatic Number of a Graph, SIAM J. Comp. 8 (1979) 1–14.

    Google Scholar 

16. Posa, L., Hamiltonian Circuits in Random Graphs, Discrete Math. 14 (1976) 359–364.

    Google Scholar 

17. Schnorr, C. P., An Algorithm for Transitive Closure with Linear Expected Time. SIAM J. Comp. 7 (1978) 127–133.

    Google Scholar 

Download references