On the Cardinal Product

Titel in Übersetzung: Über das Kardinalprodukt

Werner Klöckl

Publikation: Thesis / Studienabschlussarbeiten und HabilitationsschriftenDissertation

55 Downloads (Pure)

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
OriginalspracheEnglisch
QualifikationDr.mont.
Betreuer/-in / Berater/-in
  • Imrich, Wilfried, Beurteiler A (intern)
  • Klavžar, Sandi, Beurteiler B (extern), Externe Person
PublikationsstatusVeröffentlicht - 2007

Bibliographische Notiz

gesperrt bis null

Schlagwörter

  • Kardinalprodukt Primfaktorzerlegung Algorithmus
  • polynomialer Automorphismen Unterscheidungszahl Produkt
  • starkes

Dieses zitieren