8.3 Initializing Minimum Degree Vertex Tracking

The following data structure is proposed to support efficient tracking the minimum degree vertex during sequential vertex elimination:

  • A mapping λ\lambda between each vertex in VGV(G) and its degree.

  • A list LL which orders VGV^{\prime}(G^{\prime}) by ascending degree.

Algorithm 17 initializes this data structure for the graph GG based on its adjacency list AGA(G) and vertex list VGV(G). Observe that, per the comments in Section 8.2, AGA(G) is unchanged by this operation.

Algorithm 17: Initialize Minimum Degree Vertex Tracking
compute_degree(A,V,λA,V,\lambda)
k=k=first(VV)
while keolk\neq eol
   x=vx=v
   link(L,eolL,eol)
   k=k=next(V,kV,k)
merge_sort(L,λL,\lambda)

The procedure compute_degree creates the vertex degree mapping λ\lambda based on AGA(G) and VGV(G). Algorithm 13 is a candidate for compute_degree.

The procedure merge_sort sorts the list LL based on the mapping λ\lambda. Its name suggests that a merge sort may be the appropriate sorting algorithm. The minimum number of comparisons required to sort a set of nn keys is n ln n{n}\mbox{ }\ln\mbox{ }{n}. The merge sort algorithm is On ln nO(n\mbox{ }\ln\mbox{ }n) in both its best and worst case and is particularly suited for use with linked lists. Furthermore, merge sort does not suffer from the potentially catastrophic worst case stack growth that is common in recursive sorting algorithms. The depth of recursion of a merge sort is bounded by log n\log\mbox{ }n. This implies that sorting 1,000,000 items would require no more than 20 nested function calls. An efficient implementation of merge sort needs at most 4 to 8 bytes of local stack space for each level of recursion.