Stabilization algorithms are useful tools for perceiving the symmetries of graphs and for recognizing whether two graphs are equivalent or not. These problems are known as the graph automorphism and the graph isomorphism problem, respectively. Stabilization algorithms are also used for computing basis of coherent algebras. Furthermore, stabilization algorithms have several applications in chemistry, for example recognizing the symmetries and the structure of chemical compounds. A new application is the reconstruction of phylogenies in chemical biology. This thesis introduces an efficient way of computing 1- and 2-stable partitions. Moreover, a particular version of a k-dimensional stabilization algorithm is presented. Several aspects of stabilization procedures are considered. We discuss bounds on the number of steps and capabilites of k-dimensional stabilization algorithms. One Chapter deals with applications. A class of graphs is investigated which is of importance for the problem of reconstructing phylogenies. Other applications concern graph isomorphism, automorphism and canonical labeling problems. Then some graph classes are presented for which the isomorphism problem is solvable in polynomial time. We exhibit and discuss stabilization algorithms used in chemistry. Finally, some refinements of the algorithms and computational results are given.
«
Stabilization algorithms are useful tools for perceiving the symmetries of graphs and for recognizing whether two graphs are equivalent or not. These problems are known as the graph automorphism and the graph isomorphism problem, respectively. Stabilization algorithms are also used for computing basis of coherent algebras. Furthermore, stabilization algorithms have several applications in chemistry, for example recognizing the symmetries and the structure of chemical compounds. A new application...
»
Translated abstract:
Stabilisierungs-Algorithmen sind nützliche Hilfsmittel zum Berechnen von Symmetrien in Graphen und um festzustellen, ob zwei Graphen äquivalent sind oder nicht. Die Probleme sind bekannt als Graphenautomporhismen- und Graphenisomorphieproblem. Stabilisierungs-Algorithmen werden auch verwendet zum Berechnen von Basen Kohärenter Algebren. Außerdem haben Stabilisierungs-Algorithmen viele Anwendungen in der Chemie. Sie werden zum Beispiel eingesetzt zum Erkennen von Symmetrieen und Strukturen chemischer Verbindungen. Eine neue Anwendung ist die Rekonstruktion von Abstammungen in der Biochemie. In dieser Arbeit werden effiziente Verfahren zum Berechnen 1- und 2-stabiler Partitionen vorgestellt. Im weiteren wird ein allgemeiner k-dimensionaler Algorithmus eingeführt. Es werden Schranken für die Anzahl der Schritte und die Leistungsfähigkeit von k-dimensionalen Stabilisierungsalgorithmen diskutiert. Im Abschnitt über Anwendungen werden Graphen untersucht die zur Rekonstruktion von Abstammungen von Bedeutung sind. Andere vorgestellte Anwedungen betreffen Graphenisomorhpie, Graphenautomorphismen und Kanonische Nummerierungsprobleme. Es werden Graphenklassen angegeben für welche das Isomorhpieproblem in polynomieller Zeit zu lösen ist. Des weiteren werden in der Chemie übliche Algorithmen untersucht und mit Stabilisierungsalgorithmen verglichen. Abschließend werden Rechenergebnisse vorgestellt.
«
Stabilisierungs-Algorithmen sind nützliche Hilfsmittel zum Berechnen von Symmetrien in Graphen und um festzustellen, ob zwei Graphen äquivalent sind oder nicht. Die Probleme sind bekannt als Graphenautomporhismen- und Graphenisomorphieproblem. Stabilisierungs-Algorithmen werden auch verwendet zum Berechnen von Basen Kohärenter Algebren. Außerdem haben Stabilisierungs-Algorithmen viele Anwendungen in der Chemie. Sie werden zum Beispiel eingesetzt zum Erkennen von Symmetrieen und Strukturen chemis...
»