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

On minimum summary representing sets in general graphs

作　　者：钟昊 陈卫东[1] ZHONG Hao;CHEN Wei-dong(School of Computer Science,South China Normal University,Guangzhou 510631,China)

机构地区：[1]华南师范大学计算机学院,广东广州510631

出　　处：《计算机工程与科学》2023年第1期113-118,共6页Computer Engineering & Science

摘　　要：在一般图中,通常基于图的拓扑结构来刻画任意2个节点之间的相似度。基于节点相似度提出概要表示集SRS的概念,从图中寻找最少节点数的概要表示集称为最小概要表示集问题。证明了在一般图中求解最小概要表示集问题是NP(非确定性多项式)难的,不太可能存在多项式时间复杂度的精确算法。基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概要表示集问题,得出近似比结果。In general graphs,the similarity between any two nodes is usually characterized based on the topological structure of the graph.Based on node similarity,this paper proposes a concept named summary representing set.Finding a summary representing set with the minimum number of nodes in a graph is called the minimum summary representing set problem.It is proved that the minimum summary representing set problem is NP-hard(non-deterministic polynomials),which means it is unlikely to exist exact algorithms with poly-nomial time.A greedy approximation algorithm with polynomial time is proposed based on submodular function,which is used to solve the minimum summary representing set problem and get the approximate results.

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

分 类 号：TP3-0[自动化与计算机技术—计算机科学与技术]