Gibt es einen Algorithmus, um den besten Satz von Paaren von Scheitelpunkten in einem gewichteten Graphen ohne Wiederholung zu finden?

Question

Gibt es einen effizienten Algorithmus, um die Menge von Kanten mit den folgenden Eigenschaften in einem vollständigen gewichteten Graphen mit einer geraden Anzahl von Ecken zu finden.

• das Set hat das kleinste maximale Kantengewicht für jede Menge, dass Fleisch der anderen Kriterien möglich
• jeder Knoten ist mit genau einer Kante in dem Satz

Alle Gewichte sind positiv

dI kann nicht von einer besser als Brute-Force, aber ich erkenne sie nicht als NP hart.

Answer 1

Eine Möglichkeit, dieses Problem in polynomialer Zeit zu lösen, ist wie folgt:

1. Sortieren der Kantengewichte in O (log E E) Zeit
2. Für jede Kante, weisen sie eine pseudo-Gewicht E‘= 2 ^ {Position in der Reihenfolge} in ~ O (E) Zeit
3. Finden Sie das Mindestgewicht perfekte Abstimmung unter pseudo-Gewichten in so etwas wie O (V ^ 3) Zeit (je nach Algorithmus Sie wählen, könnte es langsamer oder schneller sein)

Dies minimiert die größte Rand, dass die perfekte Abstimmung enthält, das ist genau das, was Sie suchen in so etwas wie O (V ^ 3) Zeit.

Quellen für wie 3 zu tun Teil sind unten
gegeben [1] http://www2.isye.gatech.edu/~wcook/ Papiere / match_ijoc.pdf
[2] http://www.cs.illinois.edu/ Klasse / SP10 / cs598csc / Vorträge / Lecture11.pdf
[3] http: //www.cs.ucl. ac.uk/staff/V.Kolmogorov/papers/blossom5.ps

mit Probe C ++ Quelle finden Sie unter http: // ciju .wordpress.com / 2008/08/10 / min-Cost-perfect-matching /

Answer 2

versuchen, diese (Ich dachte nur, das, so ich habe weder der Beweis, dass es eine optimale Antwort geben, oder ob es eine Lösung in allen Fällen erzeugen):

1. Suche nach dem schwersten Eckpunkten V (A, B)
2. Entfernen vertice V aus dem Diagramm
3. , wenn A nur mit einem einzigen anderen vertice T (A, C) verbunden ist, dann alle anderen Kanten C, wiederhole Schritt 3 mit den Kanten als auch
verbunden entfernen
4. , wenn B nur auf einen einzigen anderen vertice S (B, D) verbunden ist, zu entfernen, dann alle anderen Kanten bis D verbunden sind, in Schritt 4 mit den Kanten als auch
5. Wiederholung von Schritt # 1