You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
In the randomized General Matching code, the code only knows how to extract a perfect matching, so we add up to N additional vertices before computing the matrix inverse which blows runtime up by a factor of 8. This is unnecessary, you can instead just restrict the set of vertices to the basis found in the first run of Gaussian elimination. You also shouldn't need to run Gaussian elimination a second time. (See https://codeforces.com/blog/entry/92400). This would require rewriting matInv's interface a little.
The text was updated successfully, but these errors were encountered:
In the randomized General Matching code, the code only knows how to extract a perfect matching, so we add up to N additional vertices before computing the matrix inverse which blows runtime up by a factor of 8. This is unnecessary, you can instead just restrict the set of vertices to the basis found in the first run of Gaussian elimination. You also shouldn't need to run Gaussian elimination a second time. (See https://codeforces.com/blog/entry/92400). This would require rewriting matInv's interface a little.
The text was updated successfully, but these errors were encountered: