Errata for the paper: "Parallel Implementations of Gusfield's Cut Tree Algorithm":

The pseudocode of the MPI version of Gusfield algorithm contains the following mistake: during the tree update procedure, it checks if u > s', but these are indices of the vertices and they indicate the order in which the vertices were processed only in the sequential version. In the parallel version, which threads run asynchronously, the vertices may be processed in a different order. Therefore, to produce an equivalent
test to u > s' we suggest the following: initialize flow_i = -1 for all i \in V and test for (flow_u == -1) instead of u > s.  The test (flow_u == -1) is equivalent to u > s' if tree_s' == t' because if flow_u == -1 then the cut separating u from tree_u has not been determined yet and this is the meaning of u>s' in the sequential algorithm.

Note 1: The error only appears in the pseudocode. The C code provided in the page and used for the experiments reported in the paper always adopted the strategy described above.
Note 2: The cut tree version of Gusfield algorithm does not make the test u>s' and therefore it is not affected by this issue.
Note 3: Thanks to Nerya Or for pointing out the error.