Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
We consider three computational problems with unknown complexity status: The graph isomorphism problem, the problem of computing van der Waerden numbers and the problem of computing Ramsey numbers. For each of the problems, we devise an algorithm that we analyze with theoretical and practical means by a comparison with contemporary algorithms that solve the respective problems. The ScrewBox algorithm solves the graph isomorphism problem by a random sampling process. Given two graphs, the algorithm randomly searches an invariant that may be randomly evaluated quickly and that shows significant statistical difference on the input graphs. This invariant is gradually and adaptively constructed depending on the difficulty of the input. Isomorphism is certified by supplying an isomorphism. Non-isomorphism is certified by the ScrewBox, the invariant whose statistical behavior deviates on the input graphs, together with the appropriate statistical test. The wildcards algorithm for van der Waerden numbers solves the second problem. Its key technique is to treat colorings of integers avoiding monochromatic arithmetic progressions simultaneously by allowing ambiguity. This, together with a specific preprocessing step, forms the algorithm that is used to compute previously unknown van der Waerden numbers. The wildcards algorithm for Ramsey numbers combines the techniques and algorithms with which we approach the first two problems to solve the third problem. ; Wir entwickeln Algorithmen für drei kombinatorische Probleme unbekannter Komplexität: Das Graphisomorphieproblem, die Berechnung von van der Waerden-Zahlen und die Berechnung von Ramsey-Zahlen. Mit theoretischen und praktischen Methoden wird ein Vergleich zu bereits existierenden Algorithmen gezogen. Der Schraubenkasten, ein zertifizierender, randomisierter Graph-nicht-Isomorphie Algorithmus, führt zufällige Stichproben in zwei gegeben Graphen durch, und schließt durch Festellen von statistisch signifikant abweichendem Verhalten der gesammelten Daten auf ...