Netzwerkfluss mit neg. Kanten < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:36 Do 17.01.2008 | | Autor: | Flick |
| Aufgabe | Zu einem gegebenen gewichteten, ungerichteten Graphen G = (V,E) mit Quell- und Talknoten s,t aus V ist der kürzeste Weg von s nach t gesucht. Da die Kantengewichte auch negativ sind und nicht ausgeschlossen werden kann, dass es negative Zyklen im Graphen gibt, soll keine Kante mehr als einmal durchlaufen werden.
Ist dieses Netzwerkflussproblem in Polynomzeit lösbar? |
An obigem Problem tüftel ich nun schon eine ganze weile herum aber komme auf keinen grünen Zweig. Hier helfen weder ein Dijkstra-Algorithmus noch Bellman-Ford weiter. Ich habe auch schon probiert, letzteren zu modifizieren, funktionierte aber leider nicht.
Umgekehrt finde ich auch kaum Ähnlichkeiten zu NP-harten Problemen. Wenn man s und t verbinden würde könnte man vielleicht mit geschickten Kantengewichten eine Reduktion zum Hamiltonkreisproblem basteln, konkret kam ich da aber auch nicht weiter.
Umgekehrt: so fern liegend ist dieses Problem nicht, ist jemandem ein Paper bekannt, in dem dies schon einmal durchgespielt wurde?
Herzlichen Dank,
Flick
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:29 Do 17.01.2008 | | Autor: | koepper |
Hallo Flick,
> Zu einem gegebenen gewichteten, ungerichteten Graphen G =
> (V,E) mit Quell- und Talknoten s,t aus V ist der kürzeste
> Weg von s nach t gesucht. Da die Kantengewichte auch
> negativ sind und nicht ausgeschlossen werden kann, dass es
> negative Zyklen im Graphen gibt, soll keine Kante mehr als
> einmal durchlaufen werden.
Dieses Problem nennt sich "Elementary Shortest Path Problem", wenn du sinnvollerweise Zyklen generell ausschließt.
> Ist dieses Netzwerkflussproblem in Polynomzeit lösbar?
Es ist kein Polynomzeitalgorithmus bekannt.
Aber wenn du einen findest, lass es mich wissen 
> An obigem Problem tüftel ich nun schon eine ganze weile
> herum aber komme auf keinen grünen Zweig. Hier helfen weder
> ein Dijkstra-Algorithmus noch Bellman-Ford weiter. Ich habe
> auch schon probiert, letzteren zu modifizieren,
> funktionierte aber leider nicht.
> Umgekehrt: so fern liegend ist dieses Problem nicht, ist
> jemandem ein Paper bekannt, in dem dies schon einmal
> durchgespielt wurde?
Ich kenne eine Arbeit von Irnich/Villeneuve, in der dieses Problem unter zusätzlichen Resourceneinschränkungen behandelt wird. Sie beschränken sich dort aber auf die sog. k-zyklen-Elimination. D.h. es sind garantiert nur keine Zyklen enthalten, die kleiner sind als k Kanten. Dafür wird dort auch ein effizienter Algorithmus entwickelt.
In der Arbeit findest du auch weitere Literaturhinweise. Ich häng sie dir an: ![[a]](/images/paperclip.gif "Dateianhänge") Irnich/Villeneuve
Wenn du dazu interessante Ideen hast, schick mir bitte eine PN. Wir könnten sie hier als Thread oder ggf. per Email weiter diskutieren. Das ist nämlich ein Thema, das mich auch sehr interessiert.
LG
Will
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:53 Do 17.01.2008 | | Autor: | Flick |
Hallo Will,
da bin ich ja an den richtigen geraten! Herzlichen Dank für für die englische Bezeichnung und das angehängte Paper. Damit ist mir schon sehr geholfen.
Ich lese gleich mal drüber, aber wahrscheinlich ist mir in meiner Anwendung mit den Einschränkungen von Irnich und Villeneuve schon genüge getan, die kann ich erfüllen. Eigentlich geht es mir um ein geometrisches Problem zur Bahnplanung, das ganze graphentheoretisch zu betrachten bot sich für den Moment halt an. Insofern (da der Abgabetermin für meine Diplomarbeit näher rückt...) werde ich mich dem allgemeinen Problem die nächsten Wochen nicht mehr stellen können.
Herzlichen Dank und beste Grüße,
Flick
|
|
|
|
