×

zbMATH — the first resource for mathematics

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

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.)
PDF BibTeX XML Cite
Full Text: DOI
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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.