Is there an algorithm to find the best set of Pairs of vertices in a weighted graph without repetition?

One way to solve this problem in polynomial time is as follows: Sort the edge weights in O(E log E) time For each edge, assign it a pseudo-weight E' = 2^{position in the ordering} in ~O(E) time Find the minimum weight perfect matching among pseudo-weights in something like O(V^3) time (depending on the algorithm you pick, it could be slower or faster) This minimizes the largest edge that the perfect matching contains, which is exactly what you're looking for in something like O(V^3) time Sources for how to do part 3 are given below 1 www2.isye.gatech.edu/~wcook/papers/match... 2 cs.illinois.edu/class/sp10/cs598csc/Lect... 3 cs.ucl.ac.uk/staff/V.Kolmogorov/papers/b... with sample C++ source available at ciju.wordpress.com/2008/08/10/min-cost-p....

One way to solve this problem in polynomial time is as follows: Sort the edge weights in O(E log E) time For each edge, assign it a pseudo-weight E' = 2^{position in the ordering} in ~O(E) time Find the minimum weight perfect matching among pseudo-weights in something like O(V^3) time (depending on the algorithm you pick, it could be slower or faster) This minimizes the largest edge that the perfect matching contains, which is exactly what you're looking for in something like O(V^3) time. Sources for how to do part 3 are given below 1 www2.isye.gatech.edu/~wcook/papers/match... 2 cs.illinois.edu/class/sp10/cs598csc/Lect... 3 cs.ucl.ac.uk/staff/V.Kolmogorov/papers/b... with sample C++ source available at ciju.wordpress.com/2008/08/10/min-cost-p....

This is not an answer to the question that I have. I am not trying to find the minimum sum of edges but the set with the lowest maximum edge, I have edited the question to make this more clear – ashaw Oct 31 '10 at 15:06 1 The point of taking 2^position in the ordering is to guarantee that this does find the lowest maximum edge, since the pseudo-weight of any edge is greater than the sum of pseudoweights for lesser edges, forcing the algorithm to avoid large edges at all costs. – Yonatan N Oct 31 '10 at 15:10 ah, cool I misunderstood that.

– ashaw Oct 31 '10 at 15:33.

Try this (I just thought this up so I've got neither the proof that it will give an optimum answer or whether it will produce a solution in every cases): search for the heaviest vertices V(A, B) remove vertice V from the graph if A is only connected to a single other vertice T(A, C) then remove all other edges connected to C, repeat step 3 with those edges as well if B is only connected to a single other vertice S(B, D) then remove all other edges connected to D, repeat step 4 with those edges as well repeat from step #1.

This is the greedy algorithm that I have. I do not think that it will give the correct answer, as it is possible for the solution set to not hold the heaviest edge. – ashaw Oct 31 '10 at 14:41 @ashaw: yep, it does not always give an optimal result... – Lie Ryan Oct 31 '10 at 14:49 Example ABCD, AB:100, BC:10, CD:10, DA:10, AC:10, BD:10.

A solution set would be AC, BD, and this does not contain the heaviest edge AB. – ashaw Oct 31 '10 at 14:49 @ashaw: Actually, in that case, the algorithm would remove AB, and be left with an optimal 20-weight solution. A graph where my algorithm does not work is this: ABCD, AB:100, CD:10, AC:80, BD:80, AD:80, BC:80.

The optimal solution set is (AB,CD)=110, but the algorithm will produce suboptimal 160 solution, because it decided early on that 100 is not in the solution set. – Lie Ryan Oct 31 '10 at 14:57 ah, but that is not the problem, because we are trying to find the set with the smallest maximum edge. – ashaw Oct 31 '10 at 15:04.

One way to solve this problem in polynomial time is as follows.

Try this (I just thought this up so I've got neither the proof that it will give an optimum answer or whether it will produce a solution in every cases).

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.