Isomorphism testing for embeddable graphs through definability
Isomorphism testing for embeddable graphs through definability
复制标题
通过可定义性对可嵌入图进行同构测试
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Martin Grohe
中科院分区：
文献类型：
--
作者：
Martin Grohe
当k> 1时，k维Weisfeiler-Leman算法是判定两个给定图是否同构的一种自然而简单的组合算法。本文证明了对任意曲面S（可定向或不可定向），存在一个k _> 1，使得k维WL-算法成功地判定了可嵌入曲面S的图的同构。为了证明这一点，我们使用了WL-算法和某些有限变量逻辑中的可定义性之间的密切联系，这种联系已经由Cai，Ffirer和Immerman [7]建立。
The k-dimensional Weisfeiler-Leman algorithm, for k _> 1, is a natural and simple combinatorial algorithm at tempt ing to decide whether two given graphs are isomorphic. In this paper, we show that for every surface S (orientable or non-orientable) there is a k _> 1 such that the k-dimensional WL-algori thm succeeds to decide isomorphism of graphs embeddable in S. To prove this, we use a close connection between the WL-algori thm and definability in certain finite variable logics that has been established by Cai, Ffirer, and Immerman [7].