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 $V(G)$ and its degree.

• A list $L$ which orders $V^{\prime}(G^{\prime})$ by ascending degree.

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

The procedure compute_degree creates the vertex degree mapping $\lambda$ based on $A(G)$ and $V(G)$. Algorithm 13 is a candidate for compute_degree.

The procedure merge_sort sorts the list $L$ 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 $n$ keys is ${n}\mbox{ }\ln\mbox{ }{n}$. The merge sort algorithm is $O(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\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.