1
$\begingroup$

Are there any graphs with a known set of perfect matchings and other predefined properties, such as vertex connectivity, which can be used for testing the implementation of matching algorithms?

Algorithms for generating such kind of graphs, e.g. for generating random instances would also be considered as usable definitions of such instances.

$\endgroup$

1 Answer 1

3
$\begingroup$

Please have a look at this webpage of the LEMON software, which contains datasets as well as problem instance generators for min-cost flow problems (which you can use to generate instances of MWPM problems).

This experimental survey (also linked from the abovecited webpage) also contains a lot of useful information, which will likely also help answer some of the questions that are implicit in this question (as well as perhaps some other MWPM questions that you posed).

$\endgroup$
2
  • $\begingroup$ great links! First I was bit disappointed that the experimental survey is not accessible for free, but then I saw, that a link to a freely available preliminary version is available on the webpage that is accessed via the first link. $\endgroup$ Dec 20, 2015 at 15:23
  • $\begingroup$ sorry, I forgot to mention that a free version of the survey is also linked in there; for the benefit of others reading this post, here's the link: cs.elte.hu/egres/tr/egres-13-04.pdf $\endgroup$
    – Suvrit
    Dec 20, 2015 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.