Existe um algoritmo para encontrar o melhor conjunto de pares de vértices em um gráfico ponderado sem repetição?

Question

Existe algum algoritmo eficiente para encontrar o conjunto de arestas com as seguintes propriedades, em um grafo ponderado completo com número par de vértices.

• o conjunto tem o menor e máximo peso de borda para qualquer conjunto que atenda aos outros critérios possíveis
• cada vértice está conectado a exatamente uma aresta do conjunto

Todos os pesos são positivos

dNão consigo pensar em nada melhor do que a força bruta, mas não a reconheço como NP difícil.

Answer 1

Uma maneira de resolver esse problema no tempo polinomial é a seguinte:

1. Classifique os pesos da borda no tempo de O (e log e)
2. Para cada borda, atribua-a um pseudo-peso e '= 2^{posição na ordem} no tempo ~ o (e)
3. Encontre a combinação perfeita de peso mínimo entre os pseudo-pesos em algo como O (v^3) tempo (dependendo do algoritmo que você escolher, pode ser mais lento ou mais rápido)

Isso minimiza a maior vantagem que a correspondência perfeita contém, que é exatamente o que você está procurando em algo como O (v^3).

Fontes de como fazer a Parte 3 são dadas abaixo
[1] http://www2.isye.gatech.edu/~wcook/papers/match_ijoc.pdf
[2] http://www.cs.illinois.edu/class/sp10/cs598csc/lectures/lecture11.pdf
[3] http://www.cs.ucl.ac.uk/staff/v.kolmogorov/papers/blossom5.ps

com amostra C ++ Source disponível em http://ciju.wordpress.com/2008/08/10/min-cost-perfect-satching/

Answer 2

tente isto (acabei de pensar nisso, então não tenho a prova de que isso dará uma resposta ideal ou se produzirá uma solução em todos os casos):

1. procure os vértices mais pesados ​​​​V (A, B)
2. remova o vértice V do gráfico
3. se A estiver conectado apenas a um único outro vértice T (A, C), remova todas as outras arestas conectadas a C, repita a etapa 3 com essas arestas também
4. se B estiver conectado apenas a um único outro vértice S (B, D), remova todas as outras arestas conectadas a D, repita a etapa 4 com essas arestas também
5. repita a partir do passo 1