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 Übersetzung | Kantenrekonstruktion von Kartesischen Produkten von Graphen |
---|---|
Originalsprache | Englisch |
Gradverleihende Hochschule |
|
Betreuer/-in / Berater/-in |
|
Publikationsstatus | Veröffentlicht - 1800 |
Bibliographische Notiz
gesperrt bis nullSchlagwörter
- Kantenrekonstruktion
- Kartesisches Produkt
- Graph Algorithmen