Graph isomorphism in quasipolynomial time parameterized by treewidth
Graph isomorphism in quasipolynomial time parameterized by treewidth
复制标题
由树宽参数化的拟多项式时间内的图同构
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Daniel Wiebking
中科院分区：
文献类型：
--
作者：
Daniel Wiebking
我们扩展了巴拜的拟多项式时间图同构测试（STOC 2016），并开发了多陪集同构问题的拟多项式时间算法。多陪集同构问题的算法允许利用巴拜的群论框架内的给定输入图的图分解。
我们用它来开发一个图同构测试，运行时间为$n^{\operatorname{polylog}（k）}$，其中$n$是顶点数，$k$是给定图的最小树宽，$\operatorname{polylog}（k）$是$\operatorname{log}（k）$中的某个多项式。我们的结果推广了巴拜的拟多项式时间图同构判别法。
We extend Babai's quasipolynomial-time graph isomorphism test (STOC 2016) and develop a quasipolynomial-time algorithm for the multiple-coset isomorphism problem. The algorithm for the multiple-coset isomorphism problem allows to exploit graph decompositions of the given input graphs within Babai's group-theoretic framework.
We use it to develop a graph isomorphism test that runs in time $n^{\operatorname{polylog}(k)}$ where $n$ is the number of vertices and $k$ is the minimum treewidth of the given graphs and $\operatorname{polylog}(k)$ is some polynomial in $\operatorname{log}(k)$. Our result generalizes Babai's quasipolynomial-time graph isomorphism test.
登录
查看更多内容
DOI：
10.1145/3382082
发表时间：
2020
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
M. Grohe;D. Neuen;P. Schweitzer;D. Wiebking
通讯作者：
D. Wiebking
DOI：
10.1145/3313276.3316338
发表时间：
2019
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
P. Schweitzer;D. Wiebking
通讯作者：
D. Wiebking
排除拓扑子图的图的结构定理和同构检验
DOI：
10.1145/2213977.2213996
发表时间：
2012
期刊：
影响因子：
--
作者：
M. Grohe;D. Marx
通讯作者：
D. Marx
最小电路尺寸、图同构及相关问题
影响因子：
1.6
作者：
Allender, Eric;Grochow, Joshua A.;van Melkebeek, Dieter;Moore, Cristopher;Morgan, Andrew
通讯作者：
Morgan, Andrew