2

If you combine union by rank or union by size with e.g. path compression the amortized complexity is the same [$O(m\alpha(m,n))$]. But notice that Wikipedia uses union by rank in order to prove the upper bound $O(m\log^*(n))$ because for proof purposes the union by rank algorithm is simpler to handle. On the other hand if you are implementing such a data ...


1

The adjacency matrix $A_G$ of an undirected graph $G=(V,E)$ is defined as follows: $A_G$ is a $V \times V$ matrix, $A_G(v,v) = 0$ for all $v \in V$, and $A_G(u,v) = 1$ if $\{u,v\} \in E$ and $A_G(u,v) = 0$ if $\{u,v\} \notin E$. Two graphs $G,H$ are edge-disjoint if there doesn't exist an edge $\{u,v\}$ which belongs to both of them. That is, $G,H$ are edges-...


1

We identify a binary string with a set in the following way: $x \in \{0,1\}^n$ corresponds to the set $\{ i \in [n] : x_i = 1 \}$. In particular, $0^n$ is identified with the empty set.


1

Best analysis I've seen is by Seidel and Sharir "Top-Down Analysis of Path Compression" (SIAM J. Computing 34:3, 515-525 (2005). Still heavy going... Easier to digest is Ericson's chapter in his "Algorithms".


1

The idea is actually quite simple. Just like in the book, let us assume that the find path consists of $s$ nodes. We disregard the root (because its potential doesn't change at all after the operation) and the node we upon which find_set is called (because it may have rank 0, which means its potential might not change). This leaves us with $s-2$ nodes. Now, ...


Only top voted, non community-wiki answers of a minimum length are eligible