关于树的完美邻域集与无冗余集 (2007年)

【文件属性】：

文件名称：关于树的完美邻域集与无冗余集 (2007年)

文件大小：198KB

文件格式：PDF

更新时间：2024-06-12 23:17:25

自然科学 论文

本文首先给出了求树图T的完美邻域的多项式时间复杂度算法(A),并在此基础上证明了当s是T的任一完美邻域且▏S▏ =Θ(T),则s是T的一极大无冗余集。然后给出了由T的一极大无冗余集生成完美邻域集的多项式时间复杂度算法(B),并依此算法证明了若s为T的任一极大无冗余集,则T存在一独= 完美邻域集U且▏U▏≤▏S▏。