Titlebar

Bibliografische Daten exportieren
Literatur vom gleichen Autor
plus im Publikationsserver
plus bei Google Scholar

 

Neue Strategien zur Lösung von Isomorphieproblemen

URN zum Zitieren dieses Dokuments: urn:nbn:de:bvb:703-epub-2916-5

Titelangaben

Koch, Matthias:
Neue Strategien zur Lösung von Isomorphieproblemen.
Bayreuth , 2016 . - XIV, 178 S.
( Dissertation, 2016 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

[img] PDF
Dissertation_Matthias_Koch.pdf - Veröffentlichte Version
Available under License Creative Commons BY-NC 3.0: Namensnennung, nicht kommerziell .

Download (1564Kb)

Weitere 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 weiterer Sprache

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.

Weitere Angaben

Publikationsform: Dissertation (Ohne Angabe)
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
Fachklassifikationen: Mathematics Subject Classification Code: 68R05, 68R10, 05E18, 05C60, 68W30, 15A21
Dewey Decimal Classification: 511.5; 511.6; 512.1
Themengebiete aus DDC: 000 Informatik,Informationswissenschaft, allgemeine Werke > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Institutionen der Universität: Fakultäten > Fakultät für Mathematik, Physik und Informatik
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Institut für Informatik
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Institut für Informatik > Ehemalige Professoren
Graduierteneinrichtungen > University of Bayreuth Graduate School
Fakultäten
Graduierteneinrichtungen
Sprache: Deutsch
Titel an der UBT entstanden: Ja
URN: urn:nbn:de:bvb:703-epub-2916-5
Eingestellt am: 27 Jul 2016 06:06
Letzte Änderung: 27 Jul 2016 06:06
URI: https://epub.uni-bayreuth.de/id/eprint/2916