×
Angluin, D.; Valiant, L. G.

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

J. Comput. Syst. Sci. 18, 155-193 (1979).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0437.05040

Cited in 1 Review
Cited in 159 Documents

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
Cite Review PDF
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0286.68029
[2] Coox, S. A., The complexity of theorem proving procedures, (Proceedings of the Third Annual ACM Symposium on the Theory of Computing (1971)), 151-158 · Zbl 0253.68020
[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, (Proc. London Math. Soc., 2 (1952)), 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: Academic Press New York · Zbl 0308.05001
[9] Even, S.; Kariv, O., An \(O(n^{2.5})\) algorithm for maximum matching in general graphs, (Proceedings of the 16th IEEE Symposium on Foundations of Computer Science (1975)), 100-112
[10] Feller, W., (An Introduction to Probability Theory and its Applications, Vol. I (1968), Wiley: Wiley New York) · Zbl 0155.23101
[11] Grimmett, G. R.; McDiarmid, C. J.H., On colouring random graphs, (Proc. Cambridge Philos. Soc., 77 (1975)), 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) · Zbl 0426.90066
[13] Guimady, E. H.; Perepelica, V. A., On statistically efficient algorithms for some extremal problems from graph theory, (Tezisy III Vsesoyznoi Konferencii po Problemam Teoreticheskoi Kibernetiki. Tezisy III Vsesoyznoi Konferencii po Problemam Teoreticheskoi Kibernetiki, Novosibirsk (1974)), 125-127
[14] Hopcroft, J. E.; Paul, W. J.; Valiant, L. G., On time versus space and related problems, (16th IEEE Symposium on the Foundations of Computer Science (1975)), 57-64
[15] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum: Plenum New York), 85-104 · Zbl 0366.68041
[16] Karp, R. M., The probabilistic analysis of some combinatorial search algorithms, (Traub, J. F., Algorithms and Complexity (1976), Academic Press: Academic Press New York) · Zbl 0391.90090
[17] J. KOMLÓS AND E. SZEMERÉDI; J. KOMLÓS AND E. SZEMERÉDI
[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, (Traub, J. F., Algorithms and Complexity (1976), Academic Press: Academic Press New York) · Zbl 0182.33602
[25] Chnorr, C. P., Optimal algorithms for self-reducible problems, (Michaelson, S.; Milner, R., Proceedings of the Third International Colloquium on Automata, Languages and Programming (1976), Edinburgh Univ. Press: Edinburgh Univ. Press Edinburgh), 322-337
[26] Slisenko, A. O., String-matching in real time (1977), USSR Academy of Science: 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?, (Proc. Amer. Math. Soc., 41 (1973)), 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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.