Isomorphism of graphs of bounded valence can be tested in polynomial time. (English) Zbl 0493.68064


68R10 Graph theory (including graph drawing) in computer science
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Atkinson, M.D., An algorithm for finding the blocks of a permutation group, Math. comp., 29, 911-913, (1975) · Zbl 0311.20004
[2] Babai, L., Monte-Carlo algorithms in graph isomorphism testing, (1979), manuscript
[3] Babai, L., Moderately exponential bound for graph isomorphism, (), in press · Zbl 0462.68040
[4] {\scL. Babai, P. J. Cameron, and P. P. Pálfy}, On the order of primitive permutation groups with bounded nonabelian composition factors, to appear. 5.|{\scL. Babai and E. Luks}, A subexponential algorithm for tournament isomorphism, to appear.
[5] Cameron, P.J., Finite permutation groups and finite simple groups, Bull. London math. soc., 13, 1-22, (1981) · Zbl 0463.20003
[6] Carter, R.; Fong, P., The Sylow 2-subgroups of the finite classical groups, J. algebra, 1, 139-151, (1964) · Zbl 0123.02901
[7] Furst, M.; Hopcroft, J.; Luks, E., A subexponential algorithm for trivalent graph isomorphism, () · Zbl 0462.05059
[8] Furst, M.; Hopcroft, J.; Luks, E., , polynomial-time algorithms for permutation groups, (), 36-41
[9] Hall, M., The theory of groups, (1959), Macmillan Co New York
[10] Hoffman, C.M., Testing isomorphism of cone graphs, (), 244-251
[11] Huppert, B., Endliche gruppen I, (1967), Springer-Verlag Berlin · Zbl 0217.07201
[12] {\scP. Klingsberg, E. Luks}, Succinct certificates for a class of graphs, to appear.
[13] Lipton, R.J., The beacon set approach to graph isomorphism, SIAM J. comput., 9, (1980)
[14] Luks, E., Isomorphism of graphs of bounded valence can be tested in polynomial time, (), 42-49 · Zbl 0493.68064
[15] {\scE. Luks}, The complexity of permutation group problems, to appear. · Zbl 0627.20002
[16] {\scE. Luks}, A faster algorithm for trivalent graph isomorphism, to appear. · Zbl 0462.05059
[17] Miller, G., Graph isomorphism, general remarks, J. comput system sci., 18, 128-142, (1979) · Zbl 0403.03029
[18] Miller, G.L., On the nlog n isomorphism technique, (), 51-58 · Zbl 1282.68192
[19] {\scP. P. Pálfy}, A polynomial bound for the orders of primitive solvable groups, to appear.
[20] Scott, L.L., Representations in characteristic p, (), 319-332
[21] Sims, C.C., Graphs and finite permutation groups, Math. Z., 95, 76-86, (1967) · Zbl 0244.20001
[22] Sims, C.C., Computational methods for permutation groups, (), 169-184
[23] Sims, C.C., Some group-theoretic algorithms, (), 108-124
[24] Weir, A.J., Sylow p-subgroups of the classical groups over finite fields with characteristic prime to p, (), 529-533 · Zbl 0065.01203
[25] Wielandt, H., Finite permutation groups, (1964), Academic Press New York · Zbl 0138.02501
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.