8.2 Eliminating Many Vertices

The vertex elimination procedure outlined in Algorithm 16 of Section 8.1 is primarily illustrative. When multiple vertices are eliminated, it is usually quite inefficient to create an adjacency list each time you want to eliminate a vertex from a graph.

Many of the algorithms discussed in the companion document Matrix Algorithms11https://vismor.com/documents/network_analysis/matrix_algorithms/ require an efficient vertex elimination model that supports the sequential elimination of all vertices VGV(G) from the graph G=V,EG=(V,E). The procedures are often constrained such that each stage of the process eliminates the minimum degree vertex vv from the reduced vertex set VGV^{{\prime}}(G^{{\prime}}). Additionally, the vertex elimination procedures are often prohibited the modifying of the adjacency list of the graph’s AGA(G). Recall from Section 3.2 that vertex elimination data structures must also support the following operations:

  • Increase_degree increases the degree of vertex vv by one.

  • Decrease_degree decreases the degree of vertex vv by one.

  • Remove excises vertex vv from $VGV^{\prime}(G^{\prime}) .

  • In_graph determines whether vertex vv is in VGV^{\prime}(G^{\prime}).

  • Minimum_degree finds the vertex vv in VGV^{{\prime}}(G^{{\prime}}) with the smallest degree.

Subsequent sections of this document examine the implementation of these operations.