Wie findet man in einem gerichteten Diagramm viele kleine Schnitte?

7

Die Lösung des Problems des maximalen Durchflusses ergibt einen qualifizierten minimalen Schnitt. Aber ich möchte mehrere (vielleicht Hunderte) kleine Schnitte als Kandidaten. Die Schnitte müssen keine Mindestschnitte sein, solange sie klein sind (im Gewicht). Wie mache ich das?

algorithms graphs graph-theory optimization approximation steph
quelle
Was ist klein im Gewicht? Wie viele Schnitte möchten Sie, eine konstante Zahl, , ? nn2
utdiscant
1
Um es einfach zu machen, haben alle Kanten ein Gewicht von 1 und klein bedeutet "die Anzahl der Kanten eines Schnitts ist klein, beispielsweise weniger als 10". Ich möchte zum Beispiel über n Schnitte. oder nur einige Hundert, je nachdem, was das Design erleichtert. Vielen Dank.
steph
@steph: Beachten Sie, dass bei Einheitsgewichten das Problem wahrscheinlich zu einem konzeptionell einfacheren zusammenfällt, sodass eine Lösung im allgemeinen Fall möglicherweise nicht hilfreich ist.
Raphael

Antworten:

3

Kennen Sie den randomisierten Kontraktionsalgorithmus, der auch als Karger-Algorithmus bekannt ist ? Der Algorithmus arbeitet grundsätzlich so, dass Kanten gleichmäßig zufällig ausgewählt und mit entfernten Selbstschleifen kontrahiert werden. Der Prozess wird angehalten, wenn noch zwei Knoten vorhanden sind und die beiden Knoten einen Schnitt darstellen. Um die Erfolgswahrscheinlichkeit zu erhöhen, wird der randomisierte Algorithmus mehrmals ausgeführt. Während der Läufe verfolgt man den kleinsten bisher gefundenen Schnitt.

Was ich jetzt vorschlage, ist, dass Sie den randomisierten Kontraktionsalgorithmus mehrmals ausführen. Entscheiden Sie jedes Mal, wenn der Algorithmus einen Schnitt ausgibt, ob er beibehalten werden soll oder nicht, indem Sie prüfen, ob er klein genug ist. Natürlich können Sie anhalten, wenn Sie genug von diesen ausreichend kleinen Schnitten produziert haben. Abhängig von der Größe Ihrer Eingabe kann dies in der Praxis sogar recht gut funktionieren.

Juho
quelle
Durch eine Tiefensuche anstelle einer Randomisierung kann dies auch verwendet werden, um alle minimalen Schnitte zu erhalten oder alternativ die Wahrscheinlichkeit zu erhöhen, in jeder Iteration neue Schnitte zu finden.
Raphael