Algorithm DetailΒΆ
Four algorithms are provided:
Class Name |
First Proposer |
Time Complexity |
|---|---|---|
|
\(O(n^2\textrm{MaxFlow}(n))\) |
|
|
\(O(n\textrm{MaxFlow}(n))\) |
|
|
ours |
\(O(n\textrm{MaxFlow}(n))\) |
|
ours |
\(O(n\textrm{MaxFlow}(n))\) |
Though the last three algorithms have the same level of time complexity, empirically their efficiency are different. The following picture shows the time used to get the psp structure of a dense graph \(|E|=O(|V|^2)\) generated by Gaussian blob.
