文献类型：期刊文章

作　　者：冷明[1,2] 孙凌宇[1] 边计年[2] 马昱春[2]

机构地区：[1]井冈山大学计算机科学系,江西吉安343009 [2]清华大学计算机科学与技术系,北京100084

出　　处：《小型微型计算机系统》

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

年　　份：2013

卷　　号：34

期　　号：11

起止页码：2568-2573

语　　种：中文

收录情况：AJ、BDHX、BDHX2011、CSA、CSA-PROQEUST、CSCD、CSCD2013_2014、IC、INSPEC、JST、RCCSE、SCOPUS、ZGKJHX、核心刊

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

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

分 类 号：TP391]