in the repository
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]](https://epub.uni-bayreuth.de/style/images/fileicons/application_pdf.png) |
|
||||||||
|
Download (1MB)
|
Related URLs
Abstract
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 Faculties 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 |
| URI: | https://epub.uni-bayreuth.de/id/eprint/2916 |
Download Statistics