| 10.03.2022, 16:52 |
Singularität |
Auf diesen Beitrag antworten » |
Algorithmus gesucht um einen Kreis mit Gewicht 0 zu finden
Meine Frage:
Hallo, ich suche einen polynomiellen Algorithmus für das folgende Problem: Gegeben sei ein Digraph G mit Kantengewichten c:E(G)->\mathbb(R). Gibt es einen (gerichteten) Kreis C mit Gewicht 0? Hat jemand eine Idee?
Meine Ideen:
Mein bisheriger Ansatz war es sukzessive Kreise mit niedrigstem Gewicht zu suchen und den Graph so zu verändern, dass diese Kreise nicht mehr betrachtet werden. Allerdings habe ich dies nur in O(m^m) Iterationen geschafft, wobei m die Anzahl der Kanten ist... |
