Canonisation and Definability for Graphs of Bounded Rank Width
Canonisation and Definability for Graphs of Bounded Rank Width
复制标题
有界秩宽图的规范化和可定义性
DOI：
10.1109/lics.2019.8785682
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
D. Neuen
中科院分区：
文献类型：
--
作者：
M. Grohe;D. Neuen
本文证明了维数为（3 k +4）的组合Weisfeiler-Leman算法是对所有秩宽不超过k的图类的完全同构检验。秩宽是一个图的不变量，与树宽类似，它度量图的某种层次分解的宽度;它等价于团宽。众所周知，秩宽的图的同构在多项式时间内是可判定的（Grohe and Schweitzer，FOCS 2015），但是之前已知的最好的算法对于非初等函数f有一个运行时间f（k）。我们的结果产生了一个同构测试图的秩宽度krunning在时间O（k）。我们的结果的另一个后果是第一个多项式时间的规范化算法的图有界的秩宽度。我们的第二个主要结果是，不动点逻辑计数捕获多项式时间的所有图类有界的秩宽度。
We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3k+4) is a complete isomorphism test for the class of all graphs of rank width at mostk. Rank width is a graph invariant that, similarly to tree width, measures the width of a certain style of hierarchical decomposition of graphs; it is equivalent to clique width.It was known that isomorphism of graphs of rank widthkis decidable in polynomial time (Grohe and Schweitzer, FOCS 2015), but the best previously known algorithm has a running timenf(k)for a non-elementary functionf. Our result yields an isomorphism test for graphs of rank widthkrunning in timenO(k). Another consequence of our result is the first polynomial-time canonisation algorithm for graphs of bounded rank width.Our second main result is that fixed-point logic with counting captures polynomial time on all graph classes of bounded rank width.
登录
查看更多内容
通过可定义性对可嵌入图进行同构测试
DOI：
--
发表时间：
2000
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Martin Grohe
通讯作者：
Martin Grohe
DOI：
10.1145/3382082
发表时间：
2020
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
M. Grohe;D. Neuen;P. Schweitzer;D. Wiebking
通讯作者：
D. Wiebking
使用缠结进行计算
影响因子：
0.8
作者：
Martin Grohe;Pascal Schweitzer
通讯作者：
Pascal Schweitzer
捕获区间图上的多项式时间
DOI：
10.1109/lics.2010.42
发表时间：
2010
期刊：
2010 25th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
B. Laubner
通讯作者：
B. Laubner
DOI：
10.1007/10692760_1
发表时间：
1998-06
期刊：
--
影响因子：
--
作者：
B. Courcelle;J. Makowsky;Udi Rotics
通讯作者：
B. Courcelle;J. Makowsky;Udi Rotics