Why is the cost O(|U| + sum of outgoing edges from U)? If we parallelize over all vertices in U, isn't the cost O(max out degree of any vertex in U + |result|)?
Also if we do the compare and swap as shown in the implementation of update in the bottom right corner, there actually is no need to remove duplicates from result since we won't add duplicates.
yuel1
@Kapteyn I believe the cost here is referring to the work, and you're thinking of the span.
Why is the cost O(|U| + sum of outgoing edges from U)? If we parallelize over all vertices in U, isn't the cost O(max out degree of any vertex in U + |result|)?
Also if we do the compare and swap as shown in the implementation of update in the bottom right corner, there actually is no need to remove duplicates from result since we won't add duplicates.
@Kapteyn I believe the cost here is referring to the work, and you're thinking of the span.