Zusammenfassung
Bekannte Verfahren zum Nachweis der Isomorphie zwischen zwei endlichen GraphenG undG′ benutzen Informationen über die Automorphismengruppen beider Graphen. Die vorliegende Arbeit befaßt sich mit einer systematischen Darstellung dieser Information und enthält ein Algorithmenschema zur Bestimmung der Automorphismen eines Graphen.
Abstract
Effective procedures for the decision whether two finite graphs are isomorphic or not make use of some information about the automorphism groups of these graphs. The paper deals with a systematic representation of this information and proposes an algorithm scheme for the determination of the automorphisms of a graph.
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Literatur
Unger, S. H.: GIT — A heuristic Program for Testing Pairs of Directed Line Graphs for Isomorphism. Comm. ACM7, 26–34 (1964).
Corneil, D. G., Gotlieb, C. C.: An Efficient Algorithm for Graph Isomorphism. J. ACM17, 51–64 (1970).
Knödel, W.: Ein Verfahren zur Feststellung der Isomorphie von endlichen zusammenhängenden Graphen. Computing8, 329–334 (1971).
Sirovich, F.: Isomorfismi fra grafi: un algoritmo efficiente per trovare tutti gli isomorfismi. Calcolo8, 301–337 (1971).
Levi, G.: Graph Isomorphism: A Heuristic Edge — Partitioning — Oriented Algorithm. Computing12, 291–313 (1974).
Meyer, J. F.: Algebraic Isomorphism Invariants for Graphs of Automata, Graph Theory and Computing (Read, R. C., ed.). New York-London: Academic Press. 1972.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Tinhofer, G. Zur Bestimmung der Automorphismen eines endlichen Graphen. Computing 15, 147–156 (1975). https://doi.org/10.1007/BF02252863
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02252863