On the probable behaviour of some algorithms for finding the stability number of a graph

作者：Boris G. Pittel · 发表于：Mathematical Proceedings of the Cambridge Philosophical Society · 年份：1982 · DOI：10.1017/s0305004100060205 · 被引用次数：28 · 研究领域：Complex Network Analysis Techniques、Advanced Graph Theory Research、Optimization and Search Problems

Abstract A class of f-driven algorithms due to Chvátal for finding the stability number of a graph are studied. It is shown that, for almost all graphs, the computation time grows subexponentially with n, the number of vertices. If, however, each edge exists with probability δ/n independently on other edges then asymptotically almost certainly the computation time is exponential. Still, for all large enough δ's, these algorithms perform noticeably better than a naive algorithm. The results are extended to random graphs with a fixed number of edges.