Günter Rote - Arbeiten über den algebraischen Zugang zu Graphenproblemen

Im ersten Teil der Arbeiten A systolic array algorithm for the algebraic path problem (shortest paths; matrix inversion) wird eine einheitliche algebraische Formulierung für die Matrizeninversion, für kürzeste Wege in einem Graphen, und für einige weitere Probleme mit Hilfe von Halbringen dargestellt. Dann wird daraus ein Algorithmus entwickelt. Mein Ansatz zur Darstellung des Algorithmus im Rahmen der Theorie der partiell vollständigen Halbringe unterscheidet sich in einigen Punkten von ähnlichen Ansätzen, die seit den 70er-Jahren für dieses Problem entwickelt wurden. Eine Übersicht darüber und über weitere Anwendungen habe ich im einführenden Artikel Path problems in graphs gegeben.

Die Studie The solution sets of extremal equations behandelt lineare Gleichungssysteme in denen statt der gewöhnlichen Operationen + und × die Operationen max und + stehen. Die Struktur der Lösungsmengen solcher Systeme wird untersucht, und ihre Beschreibung wird auf das Problem zurückgeführt, alle Lösungen für ein verallgemeinertes Überdeckungproblem aufzuzählen.

Die Arbeit Reachability of fuzzy matrix period behandelt das Problem, welche Perioden bei der fortlaufenden Potenzierung einer Matrix auftreten können, wenn bei der Matrizenmultiplikation statt der gewöhnlichen Operationen + und × die Operationen max und min verwendet werden. Dabei werden Fragen zur algorithmischen Komplexität mit Hilfe elementarer kombinatorischer und graphentheoretischer Methoden behandelt.

zum Überblick
Zuletzt geändert am 5. April 2002.