Algorithmus zum Entfernen der wenigsten Kanten, um die Längenzunahme des kürzesten Pfades in einem ungewichteten ungerichteten Graphen zu erzwingen

8
Gibt es eine Adjazenzmatrix für einen ungewichteten ungerichteten Graphen, gibt es einen effizienten Weg (Polynomialalgorithmus), um die Länge des kürzesten Weges zwischen irgendwelchen gegebenen zwei Knoten s und t zu erweitern / zu erhöhen?

Beispiel:

Im folgenden Beispiel gibt es 5 verschiedene 'kürzeste Wege' vom Knoten s = 1 bis zum Knoten t = 5, die jeweils die Länge 3 haben. Ich möchte die kleinste Anzahl von Kanten entfernen, so dass die kürzeste Pfadlänge erzwungen wird 4 oder mehr werden. (Das Trennen der Grafik ist in Ordnung.)

Adjazenzmatrix (erweitert um das Beispiel zu korrigieren):

%Vor%

repräsentiert dieses Diagramm:

Minimale Kosten, um die kürzeste Pfadlänge von 3 auf 4 zu erhöhen, sind die Entfernung von zwei Kanten (1,2) und (5,9)

Ziel:

Können Sie irgendwelche Ideen für einen allgemeinen Algorithmus geben, der die Menge der Kanten findet, die in einem allgemeinen Fall entfernt werden müssen?

Korrektur: Wie in meinen Kommentaren erwähnt, ist dieses Beispiel nicht vollständig. Durch Hinzufügen von zwei weiteren Scheitelpunkten 10 und 11 (in rot dargestellt) wird das Beispiel gerettet.

    
Alireza Farahani 24.01.2013, 07:44
quelle

2 Antworten

2

Ich habe es mit einem Ansatz gelöst, den ich im dritten Kommentar der Antwort "Pål GD" erwähnt habe. Hier ist der Java-Code davon. Ich hoffe, Sie finden es hilfreich!

%Vor%     
Alireza Farahani 29.05.2014, 09:37
quelle
2

Eingabe: G = (V, E), Ecken s, t und positive ganze Zahl d.

Frage: Minimiere die Anzahl der Kanten, die zum Löschen benötigt werden, so dass dist (s, t) & gt; = d.

Dieses Problem ist NP-schwer für d & gt; 3 und polynomiell lösbar für andere Werte von d.

Das Problem ist FPT parametrisiert auf der Entfernung d und der Anzahl der Kanten, die Sie löschen dürfen, k: Der Algorithmus ist wie folgt: Finden Sie einen (s, t) -Pfad der Länge am meisten d und verzweigen Sie an den d-Kanten zu dem Sie löschen können. Dies führt zu einem Algorithmus, der in der Zeit O (d ^ k * n ^ 2) läuft.

Es ist para-NP-vollständig (bzw. W [1] -hart), wenn es nur durch d (bzw. nur k) parametrisiert wird.

Ref: Pfade beschränkter Länge und ihre Schnitte: Parametrisierte Komplexität und Algorithmen, Golovach, P.A. und Thilikos, D.M., Diskrete Optimierung Band 8, Nummer 1, Seiten 72 - 86, Jahr 2011, Verlag Elsevier.

    
Pål GD 29.01.2013 21:44
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wie konfiguriert man TinyMCE, um Elemente auf Blockebene innerhalb von anchor (a) -Tags zuzulassen?