At any stage of the minimum degree algorithm, there may be more than one node with the same minimum degree, and the quality of the ordering produced may be affected by the tie breaking strategy used. In the example of Figure 7, we have deliberately broken ties in the most favorable way (with respect to parallelism); the least favorable tie breaking would have reproduced the original ordering of Figure 6, resulting in no parallelism. Breaking ties randomly (which in general is about all one can do) could produce anything in between these two extremes, yielding an elimination tree that reveals some large-grain parallelism, but which is taller and less well balanced than our example in Figure 7. Again, this is typical of minimum degree orderings. In view of this property, Liu [64] has developed an interesting strategy for further reordering of an initial minimum degree ordering that preserves fill while reducing the height of the elimination tree.

Figure 8 shows the same mesh again, this time ordered by
nested dissection, a divide-and-conquer strategy [66].
Let **S** be a set of nodes, called a * separator*, whose removal,
along with all edges incident upon nodes in **S**, disconnects
into two remaining subgraphs. The nodes in each of the two remaining
subgraphs are numbered contiguously and the nodes in the separator **S**
are numbered last. This procedure is then applied recursively to split
each of the remaining subgraphs, and so on, until all nodes have been
numbered. If sufficiently small separators can be found, then nested
dissection tends to do a good job of limiting fill, and if the pieces
into which the graph is split are of about the same size, then the
elimination tree tends to be well balanced. We see in
Figure 8 that for our example, with this ordering, the
Cholesky factor **L** suffers fill in two matrix entries (indicated by
**+**), but the elimination tree now shows a fourfold large-grain
parallelism, and its height has been reduced further. This behavior is
again typical of nested dissection orderings: they tend to be somewhat
less successful at limiting fill than minimum degree, but their
divide-and-conquer nature tends to identify parallelism more
systematically and produce better balanced elimination trees.