一般图中的最小概要表示集问题

摘要：

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

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

所属期刊栏目：45

分类号：TP3-0(计算技术、计算机技术)

在线出版日期：2023-02-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：113-118