General Weighted Perfect Matching

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm

General Weighted Perfect Matching

Post by fernando »

Hi, i wish to know how to solve the problem of finding a maximal matching with minimum weight in general graphs, (not just bipartite graphs), from comments about problem 10911, it seems to be an algorithm in O(2^n * n^2), wich uses DP, i am particularly interested in this solution, because i have not been able to identify the subproblems or the way in how the table is structured and filled, any other information is appreciated too, thanks in advance

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

I am not sure what exactly the problem is, but I am guessing you have a graph of n vertices and you're trying to pick a set of edges K, such that each vertice incidence on at most one edge of K.

Well, if it's in O(2^n * n^2) time, then here it goes:

Well, first you are given the vertices {1,2,3,4,5,6,7...,n}

You would like to pick some edge from the set, say 4 and 6 (can be any 2, in general, you can all possible pairs, which where n^2 come from)

So, now, just say in one particular case we pick (4,6), so now in this potential solution we have Cost(4,6) included in our score (that we try to maximize), and the rest of the set {1,2,3,5,7,...,n} to pick, which is our subproblem. To figure out the best set of edges you can pick from that subproblem, you recursively call the instance. Now, there are 2^n instances, thus there will be at most 2^n recursive calls, and each of them will try to pick one edge (and there are in general n^2 edges to choose from), which makes the algorithm O(2^n * n^ 2).

It is dynamic programmable because the size of your set (problem instance) sets the stage (or, optimal sub-structure) of the recursion.

Hope it helps

fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm

Post by fernando »

That was exactly the explanation i was looking for, thanks.

Post Reply

Return to “Algorithms”