文档介绍：Lecture Notes in
Computer Science
Edited by G. Goos and J. Hartmanis
136
IIIIII IIIIIIIll
Christoph M. Hoffmann
Group-Theoretic Algorithms
and Graph Isomorphism
IIII I
Springer-Verlag
Berlin Heidelberg NewYork 1982
Editorial Board
W. Brauer P. Brinch Hansen D. Gries C. Moler G. Seegm~ller
j. Stoer N. Wirth
Author
Christoph M. Hoffmann
Purdue University, Dept. puter Science
West Lafayette, !N 47907, USA
OR Subject Classifications (t979): , , ,
JSBN 3-540-t1493-9 Springer-Vedag Berlin Heidelberg New York
tSBN 0-387-1t493-9 Springer-Verlag New York Heidelberg Berlin
This work is subject to copyright. All rights are reserved, whether the whole or part of the material
is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting,
reproduction by photocopying machine or similar means, and storage in data banks, Under
§ 54 of the German Copyright Law where copies are made for other than private use, a fee is
payable to "VerwertungsgesellschaftWort °, Munich.
© by Springer-Verlag Berlin Heidelberg 1982
Printed in Germany
Printing and binding: Beltz Offsetdruck, Hemsbach/Bergstr.
2145/3140-543210
This monograph develops the recent algebraic approach to Graph Isomorphism
and some of its implications plexity. Graph Isomorphism can
be rephrased as a purely algebraic problem that exposes a surprising structural simi-
larity with a number of problems in Group Theory. These problems are easily shown
to be in NP but are not likely plete. Moreover, there is a good possibility that
they are harder than Graph Isomorphism, with respect to polynomial time reduction.
Because of this possibility, the algebraic approach detailed in this book could prove to
be very important plexity.
The roots of this approach predate Babai's Colored Graph Automorphism Problem
and my investigation of cone graphs. Nevertheless, these two papers appear to have
been the stimu