Edge-Reconstruction of Cartesian Product Graphs

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.