¿Existe un algoritmo para encontrar el mejor conjunto de pares de vértices en un grafo ponderado sin repetición?

Question

¿Hay cualquier algoritmo eficiente para encontrar el conjunto de bordes con las siguientes propiedades, en un gráfico ponderado completo con un número par de vértices.

• el conjunto tiene el, peso borde máximo más pequeño para cualquier conjunto que las carnes los otros criterios posibles
• cada vértice está conectado a exactamente un borde en el conjunto

Todos los pesos son positivos

dI no puede pensar en una mejor que la fuerza bruta, pero no lo reconocen como NP duro.

Answer 1

Una forma de resolver este problema en el tiempo polinomio es el siguiente:

1. Ordenar los pesos de las aristas en O (E log E) tiempo
2. Para cada borde, asignarle un pseudo-peso E'= 2 ^ {posición en el ordenamiento} en ~ O (E) tiempo
3. Encontrar el perfecto juego peso mínimo entre los pseudo-pesos en algo así como O (V ^ 3) tiempo (dependiendo del algoritmo que elija, que podría ser más lento o más rápido)

Esto minimiza el borde más grande que la coincidencia perfecta contiene, que es exactamente lo que está buscando en algo así como O (3 V ^) tiempo.

Las fuentes de cómo hacer la parte 3 se dan a continuación
[1] http://www2.isye.gatech.edu/~wcook/ papeles / match_ijoc.pdf
[2] http://www.cs.illinois.edu/ clase / SP10 / cs598csc / Conferencias / Lecture11.pdf
[3] http: //www.cs.ucl. ac.uk/staff/V.Kolmogorov/papers/blossom5.ps

con C muestra ++ fuente disponible en http: // ciju .wordpress.com / 2008/08/10 / min costo-perfecta coincidencia /

Answer 2

Probar (me acaba de ocurrir esto, así que tengo ni la prueba de que se le dará una respuesta óptima o si se va a producir una solución en todos los casos):

1. buscar el más pesado vértices V (A, B)
2. Eliminar vértice V a partir del gráfico
3. si A está conectado solamente a un solo otro vertice T (A, C) a continuación, quitar todos los otros bordes conectados a C, repita el paso 3 con los bordes, así
4. si B sólo está conectado a una sola de las otras vertice S (B, D) a continuación, quitar todos los otros bordes conectados a D, repita el paso 4 con los bordes, así
5. repita desde el paso # 1