Isomorphism Testing and Canonical Forms for k-Contractable Graphs (A Generalization of Bounded Valence and Bounded Genus)
Isomorphism Testing and Canonical Forms for k-Contractable Graphs (A Generalization of Bounded Valence and Bounded Genus)
复制标题
k-可收缩图的同构测试和规范形式（有界价和有界属的推广）
DOI：
10.1007/3-540-12689-9_114
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
G. Miller
中科院分区：
文献类型：
--
作者：
G. Miller
本文给出了k为固定k的k-可缩图的多项式时间同构检验和标准型，这类k-可缩图包括有界度图和有界亏格图。该算法使用了几个新的思想，包括：(1)它移除了图的一部分，并用用于跟踪这些部分的对称性的群来代替它们；(2)它与每个群保持一塔等价关系，从而允许群的分解。这些塔被称为Γk动作塔。它考虑群的典型交集。
This paper includes polynomial time isomorphism tests and canonical forms for graphs called k-contractable graphs for fixed k. The class of k-contractable graphs includes the graphs of bounded valence and the graphs of bounded genus. The algorithm uses several new ideas including: (1) it removes portions of the graph and replaces them with groups which are used to keep track of the symmetries of these portions; (2) it maintains with each group a tower of equivalence relation which allows a decomposition of the group. These towers are called a tower of Γk actions. It considers the canonical intersection of groups.