一种时间复杂度为O(m)的无向超图核值求解算法

摘要：

阐述了图核的全局信息在结点匹配中的应用,将图核理论扩展到超图上,提出了超图的核等相关概念,并给出了超图核值的形式化描述；分析了超图k水平p-核的构造性属性,给出了求解超图核值算法的基本步骤,进而讨论了降低时间复杂度的改进措施,提出了基于结点属性函数快速求解超图核值的算法框架；重点阐述了无向超图的改进压缩存储格式,将无向超图核值的求解算法从结点的度属性扩展到不同的结点属性函数,并给出了基于该存储格式的结点属性函数P5(v,U)核值求解算法,其时间复杂度为O(m),空间复杂度为O(n+m+z)；最后,基于ISPD98测试基准的18组无向超图进行了结点的度和核值的求解对比实验,其数据对比表明:核值相比结点的度更能反映出结点在超图中的重要程度.

关键词：无向超图、核值、时间复杂度、算法

所属期刊栏目：34

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金项目61063007,61163062,61106030;江西省科技支撑计划项目20132BBE50048;江西省自然科学基金项目20132BAB201035;江西省教育厅科学技术研究项目GJJ13540,GJJ12474

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

页数：共6页

页码：2568-2573