Publications by the same author
plus in the repository
plus in Google Scholar

Bibliografische Daten exportieren

Neue Strategien zur Lösung von Isomorphieproblemen

URN to cite this document: urn:nbn:de:bvb:703-epub-2916-5

Title data

Koch, Matthias:
Neue Strategien zur Lösung von Isomorphieproblemen.
Bayreuth , 2016 . - XIV, 178 P.
( Doctoral thesis, 2016 , University of Bayreuth, Faculty of Mathematics, Physics and Computer Sciences)

[thumbnail of Dissertation_Matthias_Koch.pdf]
Format: PDF
Name: Dissertation_Matthias_Koch.pdf
Version: Published Version
Available under License Creative Commons BY-NC 3.0: Attribution, Noncommercial
Download (1MB)

Related URLs


In this thesis a universal strategy to solve isomorphism problems is developed. Isomorphism problems appear in the context of many subfields of mathematics, as well as in computer science, pharmaceutics and others. The strategy is based on the homomorphism principle for group actions of Reinhard Laue and the "Snakes and Ladders" algorithm (Leiterspiel) of Bernd Schmalz. A complete mathematical basis for this strategy is given, with the so-called "Strong Ladders" at the center. In addition, three new algorithms (depthfirst StroLL, breadthfirst StroLL, Leiterspiel light) are presented on the basis of this strategy and described in pseudocode. The algorithms show the unique properties of this strategy: They are applicable for a majority of isomorphism problems, including the subgraph isomorphism problem, as well as some problems in group theory such as calculating the intersection of two subgroups; a canonical form for a single structure can be calculated; they are highly efficient and especially memory-saving; and can be executed in a distributed system. Both the mathematical strategy and the algorithms can be of interest for mathematicians as well as computer scientists and end users faced with difficult isomorphism problems.

Abstract in another language

In dieser Arbeit wird eine universelle Strategie zur Lösung von Isomorphieproblemen beschrieben. Isomorphieprobleme tauchen in vielen verschiedenen Kontexten in der Mathematik, der Informatik, der Pharmazie u.a. auf. Die Lösungsstrategie basiert auf dem Homorphieprinzip für Gruppenoperationen von Reinhard Laue und dem Leiterspielalgorithmus von Bernd Schmalz. Das mathematische Rückgrat dieser neuen Strategie wird ausführlich beschrieben, in deren Mittelpunkt die sogenannten „Starken Leitern“ stehen. Auf Basis dieser Starken Leitern werden drei neue Algorithmen (depthfirst StroLL, breadthfirst StroLL, Leiterspiel light) vorgestellt und in Pseudocode formuliert. Anhand dieser Algorithmen lassen sich die einzigartigen Eigenschaften dieser Strategie zeigen: eine Vielzahl von Isomorphieproblemen lassen sich auf diese Weise lösen wie z. B. das Teilgraphenisomorphieproblem, sowie einige Probleme der Gruppentheorie wie z.B. die Berechnung der Schnittmenge zweier Untergruppen; auch für einzelne Strukturen kann eine kanonische Form berechnet werden; sie sind sehr effizient und insbesondere speicherschonend und sind auch für die Ausführung in verteilten Systemen (distributed systems) geeignet. Sowohl die mathematische Basis als auch die Algorithmen eignen sich für Mathematiker, Informatiker und Anwender, die mit einem schwierigen Isomorphieproblem konfrontiert sind.

Further data

Item Type: Doctoral thesis (No information)
Keywords: isomorphism; group actions; combinatorial algorithms; graph isomorphism; subgraph isomorphism; discrete mathematics; construction of discrete objects; construction up to isomorphism; structure classification; group theory; graph theory; double cosets; cosets; homomorphism; strong ladders; snakes and ladders; Leiterspiel; starke Leitern; StroLL; orderly generation; canonical form; graph canonization; canonization
Subject classification: Mathematics Subject Classification Code: 68R05, 68R10, 05E18, 05C60, 68W30, 15A21
Dewey Decimal Classification: 511.5; 511.6; 512.1
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
500 Science > 510 Mathematics
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science > Former Professors
Graduate Schools > University of Bayreuth Graduate School
Graduate Schools
Language: German
Originates at UBT: Yes
URN: urn:nbn:de:bvb:703-epub-2916-5
Date Deposited: 27 Jul 2016 06:06
Last Modified: 27 Jul 2016 06:06


Downloads per month over past year