【摘 要】
：
为了在多项式时间内解决图同构问题,首先证明了2个同构图相等长度的路径信息必相同是图同构判定更为严格的必要条件.然后,根据此条件,提出了一种基于路径信息比较的图同构PIC
【机 构】
：
东南大学计算机科学与工程学院,东南大学计算机网络和信息集成教育部重点实验室
【基金项目】
：
江苏省自然科学基金资助项目(BK2012742)
论文部分内容阅读
为了在多项式时间内解决图同构问题,首先证明了2个同构图相等长度的路径信息必相同是图同构判定更为严格的必要条件.然后,根据此条件,提出了一种基于路径信息比较的图同构PIC算法.该算法依次比较各长度的路径信息,对邻接矩阵进行调整,从而实现了2个图的快速同构判定.为了减少路径信息的计算时间,引入Hash函数对PIC算法进行改进,从而得到了HPIC算法.实验结果表明,所提的2种算法均能够正确判定1×104对不同类型、不同大小的随机图是否同构,并且图同构判定的时间复杂度明显降低.HPIC算法的运行速度快于PIC算法;这2种算法在时间性能方面均优于CS算法,略劣于Nauty算法;但对于规则2维网孔图,Nauty算法失效,所提的2种算法则仍能快速进行图同构判定.
其他文献
文章把我国资本公积列报内容发展分为三个阶段,指出我国目前资本公积列报的内容混淆"资本公积"与"利得损失"之间的界限,较为杂乱无章,需要进行改革。在论述资本公积项目分类
通过临床病例分析小儿多汗分为有生理性多汗和病理性多汗即汗证两种类型。结合病案阐述了生理性多汗和病理性多汗产生的原因及防护、治疗的方法。
为了解决变压器气相色谱分析法故障诊断中存在的操作繁琐、消耗待测气体和载气、检测周期长等缺点,提出了利用光声光谱技术检测变压器油中CH4,C2H2,C2H4,C2H6,H2五种特征气体
文章通过对资金集中支付的理论研究和对南网资金管理要求的解读,结合对广东电网资金集中支付现状的实地访谈和问卷调研,总结提炼出适合广东电网公司的资金集中支付模式建议,
柏拉图＂哲学王＂思想建立在对个人、国家、世界进行划分的假设基础之上,具有两重内涵,其内涵认为只有哲学家成为统治者,或者统治者培养哲学家品质时,方能达到最好的治理效果。这
研究内部审计质量可以为我国企业提高内部审计质量,提升风险管理水平提供借鉴。文章对国外、国内内部审计质量的研究文献进行了回顾和总结,并从扩大内部审计质量评估要素、内
目的观察分析综合护理干预对脑血管CTA影像质量及效率的影响。方法于2017年10月-2018年10月在我院进行脑血管CTA检查的患者中随机选取80例设为观察对象,将其等分为观察组和对
随着全球化的到来,各国之间的文化交流日益加深,电视纪录片的传播对此功不可没。它帮助国人了解了世界文化、拓宽了视野、更新了知识。然而,语系的不同直接导致了电视纪录片
目的:了解咸阳市某医院女性乳腺癌患者的自我感受负担总体情况与服务需求,探讨个案管理介入乳腺癌患者的流程与效果.方法:采用问卷法调查20例患者;通过访谈法深度调研案主及
目的:探讨危机护理干预对影像学检查患者负面情绪的影响。方法:选取2016年5月至2018年5月我院156例行影像学检查患者为研究对象,根据抽签化原则将受试者分为对照组和研究组,