小边概率条件下较小植入团的算法

针对植入团问题是平均情况复杂性理论的一个中心问题,将带植入团的随机图模型进行推广,提出小边概率条件,使得边概率可以随着顶点数目的增大而变小.使用随机算法分析中的概率工具,改进文献中算法的分析,证明在小边概率条件下,存在以很大概率找到推广模型中较小的植入团的多项式时间随机算法.