A probabilistic analysis of some greedy cardinality matching algorithms
Tóm tắt
This paper deals with the expected cardinality of greedy matchings in random graphs. Different versions of the greedy heuristic for the cardinality matching problem are considered. Experimental data and some theoretical results are reported.
Tài liệu tham khảo
J. Edmonds, Path, trees and flowers, Can. J. Math. 17(1965)449.
C. Witzgall and C.T. Zahn, Jr., Modifications of Edmond's algorithm for maximum matching of graphs, J. Res. NBS 69b (April-June 1965)91.
H. Gabow, An efficient implementation of Edmond's maximum matching algorithm, Techn. Rep. 31 (Stanford Univ. Comp. Sci. Dept., June 1972).
J.E. Hopcroft and R. Karp, An 5/2 algorithm for maximum matchings in bipartite graphs, SIAM J. Comp. 1(1973)225.
S. Even and O. Kariv, An o(n 2.5)-algorithm for maximum matching in general graphs, Proc. 16th Ann. Symp. on Foundations of Computer Science (IEEE, New York, 1975)100.
E. Lawler, Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976).
R.E. Burkard and U. Derigs, Assignment and matching problems, in: Solution Methods with FORTRAN-Programs (Springer, Berlin-Heidelberg-New York, 1980).
D. Angluin and L.G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings, Proc. 9th ACM Symp. on Theory of Computing (1977).
D. Hausmann and B. Korte, An analysis of the greedy heuristic for independence systems, Ann. Disc. Math. 2(1978)65.
B. Bollobas and P. Erdös, Cliques in Random Graphs, Math. Proc. Camb. Phil. Soc. 80 (1976)419.