• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Sherali-Adams relaxations of graph isomorphism polytopes
【24h】

Sherali-Adams relaxations of graph isomorphism polytopes

机译：图同构多态性的Sherali-Adams弛豫

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We investigate the Sherali-Adams lift & project hierarchy applied to a graph isomorphism polytope whose integer points encode the isomorphisms between two graphs. In particular, the Sherali-Adams relaxations characterize a new vertex classification algorithm for graph isomorphism, which we call the generalized vertex classification algorithm. This algorithm generalizes the classic vertex classification algorithm and generalizes the work of Tinhofer on polyhedral methods for graph automorphism testing. We establish that the Sherali-Adams lift & project hierarchy when applied to a graph isomorphism polytope of a graph with n vertices needs Ω(n) iterations in the worst case before converging to the convex hull of integer points. We also show that this generalized vertex classification algorithm is also strongly related to the well-known Weisfeiler-Lehman algorithm, which we show can also be characterized in terms of the Sherali-Adams relaxations of a semi-algebraic set whose integer points encode graph isomorphisms.
机译：我们研究了Sherali-Adams提升和项目层次结构，该层次结构应用于图同构多形体，其整数点编码两个图之间的同构性。特别是，Sherali-Adams松弛描述了一种用于图同构的新顶点分类算法，我们称其为广义顶点分类算法。该算法推广了经典的顶点分类算法，并推广了Tinhofer在多面体方法上进行图自同构性测试的工作。我们建立了Sherali-Adams提升和项目层次结构，当应用于具有n个顶点的图的图同构多面体时，在最坏情况下需要Ω（n）迭代才能收敛到整数点的凸包。我们还表明，这种广义的顶点分类算法也与著名的Weisfeiler-Lehman算法密切相关，我们还可以用半代数集的Sherali-Adams弛豫来表征其整数点编码图同构。 。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号