Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
复制标题
树、区间图和平面图的线性时间自同构算法
DOI：
--
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
K. Booth
中科院分区：
文献类型：
--
作者：
C. Colbourn;K. Booth
基于Edmonds的测试树的同构的过程的算法被扩展到回答各种问题的自同构的标记森林。这和线性模式匹配技术被用来建立有效的算法，找到自同构分区和一组生成器的自同构群，确定自同构群的顺序，并计算森林，区间图，outerplanar图和平面图的编码。
An algorithm based upon Edmonds’s procedure for testing isomorphism of trees is extended to answer various questions concerning automorphisms of a labeled forest. This and linear pattern matching techniques are used to build efficient algorithms which find the automorphism partition and a set of generators for the automorphism group, determine the order of the automorphism group, and compute a coding for forests, interval graphs, outerplanar graphs, and planar graphs.