[Lemon-user] Enumerate all maximal/perfect matchings?

[Alpar Juttner]

Hi,

Lemon certainly has no such an algorithm, an I doubt if a polynomial
time solution exists.
The problem of counting the number of perfect matchings is at least know
to be #P-complete.

Regards,
Alpar


On Thu, 2013-09-12 at 13:28 -0400, atsuiai at aim.com wrote:
> Hello All,
> 
>    I've been using Lemon for some time now for finding maximal
> matchings, and am happy to see the August update!
> 
>    There's a particular problem I've been working on, and I don't know
> if I can solve it using Lemon or not. So, I have a general graph that
> is connected, and I'd like to enumerate over all perfect or maximal
> matchings (either is fine). The graph has a limitation that each node
> must have 1 or 2 or 3 neighbors (just 2 or 3 neighbors works as well).
> 
>     Note, my true goal is to find the average value that an edge is
> matched out of all possible configurations. So if an edge is never
> matched, it will have a value of 0, matched in a quater of the
> matchings, 0.25, etc. I do not know of a method other than enumerating
> all matchings to find this number.
> 
>    If Lemon is capable of this, please let me know! I've read over the
> documentation for the matching algorithms, and I didn't iinterpret
> anything that could be a solution. If there is even a method outside
> of lemon, I'd like to hear it! 
> 
>    Thanks for your time,
> 
>     Atsui
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user