10.3969/j.issn.1007-130X.2023.01.013
一般图中的最小概要表示集问题
在一般图中,通常基于图的拓扑结构来刻画任意2个节点之间的相似度.基于节点相似度提出概要表示集SRS的概念,从图中寻找最少节点数的概要表示集称为最小概要表示集问题.证明了在一般图中求解最小概要表示集问题是NP(非确定性多项式)难的,不太可能存在多项式时间复杂度的精确算法.基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概要表示集问题,得出近似比结果.
节点相似度、NP难、次模函数、近似算法
45
TP3-0(计算技术、计算机技术)
2023-02-15(万方平台首次上网日期,不代表论文的发表时间)
共6页
113-118