Y at-il un algorithme pour trouver le meilleur ensemble de paires de sommets dans un graphe pondéré sans répétition?

Question

Y at-il algorithme efficace pour trouver l'ensemble des arêtes avec les propriétés suivantes, dans un graphe pondéré avec un nombre pair de sommets.

• le jeu a le plus petit, le poids de bord maximum pour tout ensemble que les viandes les autres critères possibles
• chaque sommet est connecté à exactement un bord de l'ensemble

Tous les poids sont positifs

dI ne peut pas penser à une meilleure que la force brute, mais je ne reconnais pas comme NP dur.

Answer 1

Une façon de résoudre ce problème en temps polynomial est la suivante:

1. Trier les poids des arêtes en O (log E E) Temps
2. Pour chaque arête, assigner un poids pseudo-E »= 2 ^ {position dans l'ordre dans} ~ O (E) Temps
3. Trouvez la mise en correspondance de poids minimum parfaite entre poids pseudo-en quelque chose comme O (V ^ 3) temps (en fonction de l'algorithme que vous choisissez, il pourrait être plus lent ou plus rapide)

Cela permet de minimiser le plus grand bord que l'appariement parfait contient, ce qui est exactement ce que vous cherchez quelque chose comme O (V ^ 3) temps.

Sources pour savoir comment faire partie 3 sont donnés ci-dessous
[1] http://www2.isye.gatech.edu/~wcook/ papiers / match_ijoc.pdf
[2] http://www.cs.illinois.edu/ classe / SP10 / cs598csc / Conférences / Lecture11.pdf
[3] http: //www.cs.ucl. ac.uk/staff/V.Kolmogorov/papers/blossom5.ps

avec la source échantillon C ++ disponible à http: // ciju .wordpress.com / 2008/08/10 / min-coût-parfait appariement /

Answer 2

essayez ceci (je pensais juste que ce pour que je n'ai la preuve qu'il donnera une réponse optimale ou si elle produira une solution dans tous les cas):

1. rechercher les plus lourds sommets V (A, B)
2. supprimer Vertice V du graphique
3. si A est connecté uniquement à une seule autre vertice T (A, C) retirer ensuite tous les autres bords connectés à C, répéter l'étape 3 avec les bords ainsi
4. si B est connecté uniquement à une seule autre vertice S (B, D) retirer ensuite tous les autres bords connectés à D, répéter l'étape 4 avec les bords ainsi
5. répétition de l'étape 1