计算机工程与科学

作者：钟昊, 陈卫东

单位：华南师范大学计算机学院，广东 广州 510631

关键词：节点相似度,NP难,次模函数,近似算法,

在一般图中，通常基于图的拓扑结构来刻画任意2个节点之间的相似度。基于节点相似度提出概要表示集SRS的概念，从图中寻找最少节点数的概要表示集称为最小概要表示集问题。证明了在一般图中求解最小概要表示集问题是NP (非确定性多项式)难的，不太可能存在多项式时间复杂度的精确算法。基于次模函数提出了多项式时间复杂度的贪心近似算法，用于求解最小概要表示集问题，得出近似比结果。

来源：2023年第1期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2023年第1期