# 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$.

Algorithm 18: Increase the Degree of a Vertex
 increase_degree($v$) $n=$evaluate($\lambda,v$)$+1$ map($\lambda,v,n$) $i=k=$find($L,v$) while $k\neq eol$ and $n>$evaluate($\lambda,k$) $k=n$ext($L,k$) link($L,k,v$) unlink($L,i$)

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: Decrease the Degree of a Vertex
 decrease_degree($v$) $n=$evaluate($\lambda,v$)$-1$ map($\lambda,v,n$) $i=k=$find($L,v$) while $k\neq eol$ and $n<$evaluate($\lambda,k$) $k=$previous($L,k$) link($L,k,v$) unlink($L,i$)

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$.

Algorithm 20: Remove a Vertex from the Reduced Graph
 remove($v$) $i=$find($L,v$) unlink($L,i$) map($\lambda,v,0$)