Laufzeit von Dijkstra in bipartiten Graphen

Neue Frage »

plizzz Auf diesen Beitrag antworten »
Laufzeit von Dijkstra in bipartiten Graphen
Hallo,

ich habe folgendes Problem: Ich lese gerade ein Paper über Optimierung und dort taucht an einer Stelle folgender gerichteter bipartiter Graph auf:

Knotenmenge: U x V mit |U|=n, |V|=m mit n=>m

Kantenmenge: E_1= (V x U) und dazu eine Teilmenge E_2 von (U x V), von der man erstmal nichts weiter weiß

Gewichte: w(e) >= 0 (nichts weiter bekannt) für alle e aus E_1 und w(e)=0 für alle e aus E_2

Nun hat der Graph O(nm) Kanten und n+m= O(n) Knoten, da n>=m.

Daher komme ich auf auf eine Laufzeit von Dijkstra von O(nm + n * log(n)) bei Verwendung von Fibonacci-Heaps.

Nun schreibt der Autor allerdings etwas von einer Laufzeit von O(mn + m * log(m)) und führt diese darauf zurück, dass alle Kanten aus E_2 Gewicht 0 haben. Mehr als diese Bemerkung hinzuschreiben macht er allerdings nicht.

Ich habe jetzt eine Weile nachgedacht und komme nicht darauf, wie der Dijkstra mit dieser Laufzeit machbar sein soll.

Das Paper hat es übrigens wohl niemals zur Veröffentlichung geschafft und es ist wohl unklar, ob es überhaupt richtig ist. Daher kann es auch sein, dass die Aussage einfach nicht stimmt.

Außerdem entschuldige ich mich für den fehlenden Einsatz von Latex, aber da ich hier die mathematischen Ausdrücke nur im Text untergebracht habe, war es schwierig sinnvoll einzusetzen (sowas wie das "$...$" wie in normalen Dokumenten gibt es hier im Forum nicht, oder?).

Vielen Dank und freundliche Grüße,

plizzz
plizzz Auf diesen Beitrag antworten »

Ok, manchmal hilft es wohl, das Problem nur nochmal vernünftig hinzuschreiben. Ich bin jetzt von selbst auf die Lösung gekommen. Wenn es jemanden interessiert, kann ich sie hier auch hinschreiben (ist nicht sonderlich geistreich).
plizzz Auf diesen Beitrag antworten »

Muss leider nochmal updaten. Meine Lösung war nicht besonders geistreich und dann auch nicht besonders richtig. Die Frage steht also wieder im Raum.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »