• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2023, Vol. 45 ›› Issue (01): 113-118.

• 图形与图像 • 上一篇    下一篇

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

钟昊,陈卫东   

  1. (华南师范大学计算机学院,广东 广州 510631)
  • 收稿日期:2022-09-14 修回日期:2022-10-23 接受日期:2023-01-25 出版日期:2023-01-25 发布日期:2023-01-25

On minimum summary representing sets in general graphs

ZHONG Hao,CHEN Wei-dong   

  1. (School of Computer Science,South China Normal University,Guangzhou 510631,China)
  • Received:2022-09-14 Revised:2022-10-23 Accepted:2023-01-25 Online:2023-01-25 Published:2023-01-25

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

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

Abstract: 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.

Key words: node similarity, NP-hard, submodular function, approximation algorithm