Code covered by the BSD License  

Highlights from
Minimum Perfect Matching Tool

3.5

3.5 | 2 ratings Rate this file 6 Downloads (last 30 days) File Size: 1.95 KB File ID: #27181

Minimum Perfect Matching Tool

by Vojtech Knyttl

 

07 Apr 2010 (Updated 11 Aug 2010)

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

| Watch this File

File Information
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
Tags for This File  
Everyone's Tags
graphs, linear programming, matching, optimization, perfect matching
Tags I've Applied
Add New Tags Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (4)
05 May 2013 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

01 May 2013 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

08 May 2012 Marino Pagan  
20 Dec 2011 Tseng Tzu-Yueh

good

Updates
11 Aug 2010

Incident matrix => adjacent matrix.

Contact us