声明
严正声明：本站非期刊官网，非中介代理。
本站仅提供学术规范服务：快速预审、润色编辑服务、中英文查重、降重、去重服务、推荐合适的期刊投稿等学术规范服务。 如需提供学术规范服务请联系在线编辑。
国内刊号：43-1258/TP
国际刊号：1007-130X
发布日期:
作者：钟昊, 陈卫东
单位：华南师范大学计算机学院，广东 广州 510631
关键词：节点相似度,NP难,次模函数,近似算法,
在一般图中，通常基于图的拓扑结构来刻画任意2个节点之间的相似度。基于节点相似度提出概要表示集SRS的概念，从图中寻找最少节点数的概要表示集称为最小概要表示集问题。证明了在一般图中求解最小概要表示集问题是NP (非确定性多项式)难的，不太可能存在多项式时间复杂度的精确算法。基于次模函数提出了多项式时间复杂度的贪心近似算法，用于求解最小概要表示集问题，得出近似比结果。
来源：2023年第1期
《计算机工程与科学》期刊编辑部
严正声明：本站非期刊官网，非中介代理。
本站仅提供学术规范服务：快速预审、润色编辑服务、中英文查重、降重、去重服务、推荐合适的期刊投稿等学术规范服务。 如需提供学术规范服务请联系在线编辑。