基于计算群论改进图最大等价划分搜索算法

《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号