Fast probabilistic algorithms for Hamiltonian circuits and matchings. (English) Zbl 0437.05040

Angluin, D.; Valiant, L. G.

J. Comput. Syst. Sci. 18, 155-193 (1979).

MSC:

05C45	Eulerian and Hamiltonian graphs
68Q25	Analysis of algorithms and problem complexity
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

probabilistic behaviour; Hamiltonian circuit; random graph; perfect matching

References:

[1]	Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0286.68029
[2]	Coox, S.A., The complexity of theorem proving procedures, (), 151-158
[3]	Cook, S.A.; Reckhow, R.A., Time-bounded random access machines, J. comput. system sci., 7, 354-375, (1973) · Zbl 0284.68038
[4]	Dirac, G.A., Some theorems on abstract graphs, (), 69-81 · Zbl 0047.17001
[5]	Edmonds, J., Paths, trees, and flowers, Canad. J. math., 17, 449-467, (1965) · Zbl 0132.20903
[6]	Erdös, P.; Rényi, A., On random graphs I, Publ. math. debrecen, 6, 290-297, (1959) · Zbl 0092.15705
[7]	Erdös, P.; Rényi, A., On the existence of a factor of degree one of connected random graphs, Acta math. acad. sci. hungar., 17, 359-379, (1966) · Zbl 0203.56902
[8]	ErdÖs, P.; Spencer, J., Probabilistic methods in combinatorics, (1974), Academic Press New York · Zbl 0308.05001
[9]	Even, S.; Kariv, O., An O(n2.5) algorithm for maximum matching in general graphs, (), 100-112
[10]	Feller, W., ()
[11]	Grimmett, G.R.; McDiarmid, C.J.H., On colouring random graphs, (), 313-324 · Zbl 0297.05112
[12]	Guimady, E.H.; Glebov, N.I.; Perepelica, V.A., Algorithms with bounds for problems of discrete optimizations, Problemy kibernet., 31, 35-52, (1976)
[13]	Guimady, E.H.; Perepelica, V.A., On statistically efficient algorithms for some extremal problems from graph theory, (), 125-127
[14]	Hopcroft, J.E.; Paul, W.J.; Valiant, L.G., On time versus space and related problems, (), 57-64
[15]	Karp, R.M., Reducibility among combinatorial problems, (), 85-104 · Zbl 0366.68041
[16]	Karp, R.M., The probabilistic analysis of some combinatorial search algorithms, () · Zbl 0391.90090
[17]	{\scJ. KOMLÓS AND E. SZEMERÉDI}, private communication.
[18]	Koršunov, A.D., On the power of some classes of graphs, Soviet math. dokl., 11, 1100-1104, (1970) · Zbl 0211.56902
[19]	Koršunov, A.D., Solution of a problem of Erdös and Rényi on Hamiltonian cycles in nonoriented graphs, Soviet math. dokl., 17, 760-764, (1976) · Zbl 0353.05039
[20]	Lev, G., Reversible concatenable lists, (1976), Department of Computer Science, University of Edinburgh, manuscript
[21]	Levin, L.A., Universal combinatorial problems, Problemy peredači informacii, 9, 115-116, (1972) · Zbl 0313.02026
[22]	Perepelica, V.A., On two problems from the theory of graphs, Soviet math. dokl., 11, 1376-1379, (1970) · Zbl 0214.51702
[23]	Posh, L., Hamiltonian circuits in random graphs, Discrete math., 14, 359-364, (1976) · Zbl 0322.05127
[24]	Rabin, M.O., Probabilistic algorithms, () · Zbl 0182.33602
[25]	Chnorr, C.P., Optimal algorithms for self-reducible problems, (), 322-337
[26]	Slisenko, A.O., String-matching in real time, (1977), USSR Academy of Science Leningrad, Preprint R-7-77 of LOMI · Zbl 0359.02035
[27]	Solovay, R.; Strassen, V., A fast Monte-Carlo test for primality, SIAM J. comput., 6, 84-85, (1977) · Zbl 0345.10002
[28]	Wright, E.M., For how many edges is a digraph almost certainly Hamiltonian?, (), 384-388, 2 · Zbl 0272.05112
[29]	Wright, E.M., Graphs on unlabelled nodes with a given number of edges, Acta math., 126, 1-9, (1971) · Zbl 0204.57202