Timeline for Complexity of maximum weight-sum matching for cycle graphs
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 2 at 16:09 | answer | added | Manfred Weis | timeline score: 1 | |
| Apr 1 at 18:20 | comment | added | RobPratt | You might as well omit any edges with nonpositive weight. It might also be interesting to compare the DP approach to the natural (set packing) IP approach with a binary variable for each edge and a conflict constraint for each node. | |
| Apr 1 at 15:35 | comment | added | Manfred Weis | @dbal thanks for the hint to the trees; I think that generalizes to an O(n) algorithm for cycles; if we duplicate say vertex 0 an make that the start and lend of a path, the we can have three cases: a) the first edge but not the last edge is in the matching; b) the last but not the first edge is in the matching; c) neither the first nor the last edge is in the matching. | |
| Apr 1 at 14:17 | comment | added | dbal | Apparently there are O(n) dynamic programming algorithms for trees. (math.stackexchange.com/questions/320481/…) So you could iterate over each edge and apply the DP algorithm on the remaining path. This gives a O(n^2) algo. | |
| Apr 1 at 13:26 | history | asked | Manfred Weis | CC BY-SA 4.0 |