Esiste un algoritmo per trovare il miglior set di coppie di vertici in un grafo pesato senza ripetizione?

Question

Esiste un algoritmo efficiente per trovare l'insieme di bordi con le seguenti proprietà, in un grafo pesato completa con un numero pari di vertici.

• l'insieme ha il più piccolo, peso massimo bordo per ogni insieme che carni gli altri criteri possibili
• ogni vertice è collegato ad un bordo esattamente nel set

Tutti i pesi sono positivi

dI non si può pensare di meglio di forza bruta, ma non riconoscerlo come NP difficile.

Answer 1

Un modo per risolvere questo problema in tempo polinomiale è la seguente:

1. Ordinare i pesi bordo in O (log E E) tempo
2. Per ogni bordo, assegnare un pseudo-peso E'= 2 ^ {posizione nell'ordinamento} in ~ O (E) Tempo
3. trova i corrispondenti peso minimo tra pseudo-pesi in qualcosa di simile a O (V ^ 3) tempo (a seconda dell'algoritmo si sceglie, si potrebbe essere più lento o più veloce)

Questo riduce al minimo il bordo più grande che l'abbinamento perfetto contiene, che è esattamente quello che stai cercando in qualcosa di simile a O (V ^ 3) tempo.

Fonti per come fare parte 3 Di seguito sono riportati
[1] http://www2.isye.gatech.edu/~wcook/ carte / match_ijoc.pdf
[2] http://www.cs.illinois.edu/ classe / SP10 / cs598csc / Conferenze / Lecture11.pdf
[3] http: //www.cs.ucl. ac.uk/staff/V.Kolmogorov/papers/blossom5.ps

con il campione C ++ sorgente disponibile presso http: // ciju .wordpress.com / 2008/08/10 / min-costo-perfetto-matching /

Answer 2

provare questo (ho pensato questo in modo ho né la prova che darà una risposta ottimale o se esso produrrà una soluzione in tutti i casi):

1. cercare il più pesante vertici V (A, B)
2. rimuovi vertice V dal grafico
3. se A è collegato a un solo altro vertice T (A, C) quindi rimuovere tutti gli altri bordi collegati a C, ripetere la fase 3 con i bordi così
4. se B è collegato ad un solo altro vertice S (B, D) quindi rimuovere tutti gli altri bordi collegati a D, ripetere passaggio 4 con i bordi così
5. Ripetere dal punto # 1