基于计算群论改进图最大等价划分搜索算法
《Symmetry》:Improved Exact Algorithm for Finding a Maximum Exploratory Equivalent Partition
【字体:
大
中
小
】
时间:2026年09月26日
来源:Symmetry 2.2
摘要
具有非平凡自同构的图 G 的一个探索性等价划分(EE 划分)是其顶点集的一个划分,该划分可以直接转化为一组约束条件,从而加速在任意宿主图中搜索 G 出现次数的过程。最大 EE 划分问题旨在寻找能带来最大加速效果的 EE 划分。然而,该问题是 NP 困难的,且朴素算法仅适用于规模较小但具有丰富对称性的图。在本文中,我们提出了一系列基于计算群论的改进方法,大幅扩展了该算法的适用范围。例如,改进后的算法在 10-超立方体图(1024 个顶点、5120 条边、约 3.7 个自同构) 上的运行时间,比朴素算法在 4-超立方体图(16 个顶点、32 条边、384 个自同构)上的运行时间还要短。我们证明了所有改进均能保持算法的正确性,并通过大量实验验证了它们对执行速度的贡献。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号