Message-Routing in Würfeln Laufzeitanalyse

Hallo zusammen,

das Informatik-Forum geht in den Archivmodus, genaue Informationen kann man der entsprechenden Ankündigung entnehmen. Als Dankeschön für die Treue bekommt man von uns einen Gutscheincode (informatikforum30) womit man bei netzliving.de 30% auf das erste Jahr sparen kann. (Genaue Infos sind ebenfalls in der Ankündigung)

Vielen Dank für die Treue und das Verständnis!

    Also da ich hier keinen Thread zur LaufzeitAnalyse gefunden habe, packe ich den kram einfach mal hier rein.

    Sei G ein Netzwerk von n Prozessoren. Jeder Prozessor in G habe höchstens d Nachbarn. Sei w weiterhin A ein konservativer, determinisstischer Routing-Algorithmus. Dann gibt es eine Permutation π für die A mindestens Ω (Wurzel(n/d)) Schritte benötigt.


    Nun meine Frage: Warum ist Ω (Wurzel(n/d))?

    Google ist dein Freund ;)
    schau dir folgendes Paper an:
    C. Kaklamanis, D. Krizanc und T. Tsantilas, Tight bounds for oblivious routing
    in the hypercube, Proceedings of the 3rd Symposium on Parallel Algorithms und
    Architectures, pp. 31-36, 1991