Timeline for Counting number of perfect matchings
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 5, 2023 at 1:40 | comment | added | Brendan McKay | Consider one component, which consists of a cycle with trees attached to each vertex. A leaf edge must be in the p.m., so repeatedly remove leaf edges and both their vertices. If an isolated vertex occurs, the count is 0. Otherwise it will end when there is nothing left or just the cycle left. If nothing is left the count is 1, if an odd cycle 0, even cycle 2. Multiply the counts for each component. It's obviously polynomial. To achieve linear time, it needs a good data structure to keep track as the leaf edges are removed. | |
| Jun 3, 2023 at 15:28 | comment | added | Turbo | @BrendanMcKay Can you explain the linear time algorithm? | |
| Jun 3, 2023 at 8:49 | comment | added | Brendan McKay | Per Fedor, if the subdivided graph has a perfect matching then every component has a unique cycle. For such graphs computing the number of perfect matchings can be done in linear time. Alternatively, subdivide each edge of $G$ with two new vertices. Now the number of perfect matchings is the same as for $G$. | |
| Jun 3, 2023 at 6:10 | comment | added | Fedor Petrov | Usually new graph have unequal parts | |
| Jun 3, 2023 at 6:04 | history | edited | YCor |
edited tags
|
|
| Jun 3, 2023 at 1:10 | history | asked | Turbo | CC BY-SA 4.0 |