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

Algorithm 18: Increase the Degree of a Vertex
increase_degree(vv)
   n=n=evaluate(λ,v\lambda,v)+1+1
   map(λ,v,n\lambda,v,n)
   i=k=i=k=find(L,vL,v)
   while keolk\neq eol and n>n>evaluate(λ,k\lambda,k)
      k=nk=next(L,kL,k)
   link(L,k,vL,k,v)
   unlink(L,iL,i)

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

Algorithm 19: Decrease the Degree of a Vertex
decrease_degree(vv)
   n=n=evaluate(λ,v\lambda,v)-1-1
   map(λ,v,n\lambda,v,n)
   i=k=i=k=find(L,vL,v)
   while keolk\neq eol and n<n<evaluate(λ,k\lambda,k)
      k=k=previous(L,kL,k)
   link(L,k,vL,k,v)
   unlink(L,iL,i)

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

The remove operator (Algorithm 20) excises vv from the degree list LL 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(vv)
   i=i=find(L,vL,v)
   unlink(L,iL,i)
   map(λ,v,0\lambda,v,0)