Edge-Reconstruction of Cartesian Product Graphs

Titel in Übersetzung: Kantenrekonstruktion von Kartesischen Produkten von Graphen

Marcin Jacek Wardynski

Publikation: Thesis / Studienabschlussarbeiten und HabilitationsschriftenDissertation

Abstract

Diese Thesis löst das Problem der schwachen Kantenrekonstruktion von Kartesischen Produkten. Anders gesagt, es wird gezeigt, dass ein beliebiges endliches oder unendliches Kartesisches Produkt G mit der Kantenmenge E(G) durch jeden beliebigen Teilgraphen {G − e|e ∈ E(G)}, abgesehen von Isomorphismen, eindeutig bestimmt ist. Für endliche Kartesische Produkte präsentiert die Thesis auch einen Algorithmus für die Berechnung von G anhand von G – e in O(m∆²) Zeit, wo m und ∆ für die Kantenzahl und den höchsten Grad stehen. Der neue Ansatz verbessert den direkten Algorithmus für die Rekonstruktion von G, der die Komplexität O(mn²) hat, wobei n für die Knotenzahl von G steht. Weil ∆ viel kleiner als n sein kann, ist das eine wesentliche Verbesserung.
Titel in ÜbersetzungKantenrekonstruktion von Kartesischen Produkten von Graphen
OriginalspracheEnglisch
Gradverleihende Hochschule
  • Montanuniversität
Betreuer/-in / Berater/-in
  • Imrich, Wilfried, Beurteiler A (intern)
  • Aurenhammer, Franz, Beurteiler B (extern), Externe Person
PublikationsstatusVeröffentlicht - 1800

Bibliographische Notiz

gesperrt bis null

Schlagwörter

  • Kantenrekonstruktion
  • Kartesisches Produkt
  • Graph Algorithmen

Dieses zitieren