A subexponential algorithm for trivalent graph isomorphism
Cornell University, May, 1980 - Graph theory - 62 pages
This report contains two results: First, a polynomial-time algorithm to test color preserving isomorphism of two vertex-colored graphs in which each color class is of size k or less; Second, we improve Hoffman's algorithm for determining the automorphism group of a trivalent cone graph to deterministic time 0(n(clogn)) and extend it to arbitrary trivalent graphs. (Author).
What people are saying - Write a review
We haven't found any reviews in the usual places.
Computing the Intersection of Two Groups
Cone Graphs and Hoffmann s Algorithm
2-group 2SSG of SQ A^+j algorithm for computing algorithm for testing ALGORITHM FOR TRIVALENT automorphism group automorphisms of G bounded color multiplicity canonical form CHAPTER complete binary tree computing the automorphism construct determined in polynomial deterministic algorithm disjoint sets domains of imprimitivity double cone graph edge fixed found in polynomial G and H graph G graph isomorphism problem graph isomorphism testing graphs with bounded group of G groups in polynomial Groups of order Hoffmann's algorithm Hopcroft leaves of subtrees Let G level i vertices level i+1 maps Merrick Lee Furst permutation group polynomial-time algorithm polynomial-time reduced polynomially accessible tower Proof recognizable groups sets of imprimitivity sift(x SQ containing G SUBEXPONENTIAL ALGORITHM subgroup of G subtrees of height successively more vertices Syl(A Sylow subgroup testing isomorphism Theorem Sylow tower from Syl(G tower of groups trivalent graph isomorphism vertex vertex-colored graphs vertices of G written in canonical