Minimum Perfect Matching Tool

Function to solve the Minimum Perfect Matching Problem on non-biparite graphs.

Description

Function to solve the Minimum Perfect Matching on non-biparite graphs problem using Integer linear programming.

Returns vector of matched indices and cost of the match. Requires symmetric adjacent matrix of even rank.
 
function [ indices, cost ] = min_perfect_matching( G )

Function _requires_ integer linear programming tool "mixed-integer LP" by Sherif Tawfik, available at:

http://www.mathworks.com/matlabcentral/fileexchange/6990-mixed-integer-lp

• Required Products: Optimization Toolbox
• MATLAB release: MATLAB 7.8 (R2009a)
• Other requirements: "mixed-integer LP" by Sherif Tawfik, available at: http://www.mathworks.com/matlabcentral/fileexchange/6990-mixed-integer-lp

[Kasper]

I have my matrix input looking like this
G=
[0 250 0 570 0 0 0 0 0 0
250 0 440 0 560 0 0 0 0 0
0 440 0 0 0 390 0 0 0 0
570 0 0 0 270 0 220 0 0 0
0 560 0 270 0 420 0 0 0 0
0 0 390 0 420 0 0 0 500 0
0 0 0 220 0 0 0 250 0 0
0 0 0 0 0 0 250 0 400 590
0 0 0 0 0 500 0 400 0 430
0 0 0 0 0 0 0 590 430 0]

>> min_perfect_matching(G)

Then i get a long row including 0s and 5x1s and then this vector how do i tell which vertices were matched?

ans =

10 4 9 2 7 8 5 6 3 1

[Maartje]

I tried to use this file but I get the following error.

??? undefined function or method 'prod'for input arguments of type 'uint16'.

Error in ==>repmat at 49
nelems=prod(size);

Error in ==> min_perfect_matching at 61
ctype=repmat('S',1,len); % equalities

I also downloaded IP and added that in my Current Directory.

Does anybody now the cause of this problem and how to solve it?

Thanx a lot

[Marino Pagan]

 

[Tseng Tzu-Yueh]

good