8.4 Maintaining the Reduced Graph

With the vertex elimination data structure established, maintenance and query operations are straightforward. Algorithm 18 implements increase_degree. It assumes the list communication buffer is $x$.

In words, Algorithm 18 increases the degree of $v$ and scans the degree list $L$ in ascending order until the new position of $v$ is located. It then adds $v$ into $L$ at this position and deletes $v$ from the old position. In the worst case, the loop in Algorithm 18 is an $O\left(|V^{{\prime}}|\right)$ operation. This degenerate case only occurs when all vertices in $V^{{\prime}}(G^{{\prime}})$ have the same degree and $v$ is the first item in $L$.

Algorithm 19 implements the decrease_degree operation. It decreases the degree of $v$ then scans the degree list $L$ in descending order until the new position of $v$ is located. It then adds $v$ into $L$ at this position and deletes $v$ from the old position. Once again, Algorithm 19 is an $O\left(|V^{{\prime}}|\right)$ in the worse case. In the average case, it is much closer $O(1)$.

The remove operator (Algorithm 20) excises $v$ from the degree list $L$ and makes sure its degree count is less than or equal to zero in the mapping $\lambda$.