Abstract
Ziel der Dissertation ist die Entwicklung von Algorithmen zur Faktorisierung von Graphen bezüglich des Kardinal- und des Starken Produktes. Für jedes dieser Produkte wird ein Algorithmus entwickelt. Der für das Starke Produkt wendet den polynomialen Algorithmus von Feigenbaum und Schäffer lokal an und verbessert damit die globale Komplexität. Der für das Kardinalprodukt entwickelte Algorithmus ist der bisher einzige, der die Primfaktorzerlegung eines gerichteten Graphen bezüglich des Kardinalproduktes in polynomialer Zeit ermöglicht. Die Korrektheit des Algorithmus impliziert auch die Eindeutigkeit der Primfaktorisierung. Damit wird die Klasse aller gerichteten Graphen, von welchen die Eindeutigkeit der Primfaktorzerlegung bekannt ist, erweitert. Um den Algorithmus zu verallgemeinern, wird eine völlig neue Klasse von Graphen, sogenannter R^+_{r,s} - Graphen, eingeführt und erforscht. Unsere Faktorisierungsresultate erlauben auch eine Beschreibung der Automorphismengruppe von gerichteten Kardinalprodukten. Diese Strukturbeschreibung verwendend, berechnen wir Unterscheidungszahlen von Graphen.
Titel in Übersetzung | Über das Kardinalprodukt |
---|---|
Originalsprache | Englisch |
Qualifikation | Dr.mont. |
Betreuer/-in / Berater/-in |
|
Publikationsstatus | Veröffentlicht - 2007 |
Bibliographische Notiz
gesperrt bis nullSchlagwörter
- Kardinalprodukt Primfaktorzerlegung Algorithmus
- polynomialer Automorphismen Unterscheidungszahl Produkt
- starkes