A unifying method for the design of algorithms canonizing combinatorial objects
A unifying method for the design of algorithms canonizing combinatorial objects
复制标题
一种标准化组合对象算法设计的统一方法
DOI：
10.1145/3313276.3316338
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
D. Wiebking
中科院分区：
文献类型：
--
作者：
P. Schweitzer;D. Wiebking
我们设计了一个统一的框架规范化算法的设计。使用遗传有限集，我们定义了一个一般概念的组合对象，包括图，超图，关系结构，代码，置换群，树分解，等等。我们的方法允许系统转移的技术，已开发的同构测试，规范化。我们使用它来设计一般组合对象的经典化算法。这一结果给出了新的最快的标准化算法与渐近运行时间匹配的最知名的同构算法为以下类型的对象：超图，超图的有界颜色类大小，置换群（置换同构）和代码，明确给出（代码等价）。
We devise a unified framework for the design of canonization algorithms. Using hereditarily finite sets, we define a general notion of combinatorial objects that includes graphs, hypergraphs, relational structures, codes, permutation groups, tree decompositions, and so on.Our approach allows for a systematic transfer of the techniques that have been developed for isomorphism testing to canonization. We use it to design a canonization algorithm for general combinatorial objects. This result gives new fastest canonization algorithms with an asymptotic running time matching the best known isomorphism algorithm for the following types of objects: hypergraphs, hypergraphs of bounded color class size, permutation groups (up to permutational isomorphism) and codes that are explicitly given (up to code equivalence).
登录
查看更多内容
DOI：
10.1145/3382082
发表时间：
2020
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
M. Grohe;D. Neuen;P. Schweitzer;D. Wiebking
通讯作者：
D. Wiebking
k-可收缩图的同构测试和规范形式（有界价和有界属的推广）
DOI：
10.1007/3-540-12689-9_114
发表时间：
1983
期刊：
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
G. Miller
通讯作者：
G. Miller
打破 p 群同构的生成器枚举界限
DOI：
10.1016/j.tcs.2015.05.036
发表时间：
2013
期刊：
ArXiv
影响因子：
--
作者：
David J. Rosenbaum;Fabian Wagner
通讯作者：
Fabian Wagner
没有阿贝尔正规子群的群的多项式时间同构检验 -（扩展摘要）
DOI：
10.1007/978-3-642-31594-7_5
发表时间：
2012
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
L. Babai;Paolo Codenotti;Youming Qiao
通讯作者：
Youming Qiao
DOI：
--
发表时间：
1999
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
E. Luks
通讯作者：
E. Luks