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 from the graph . The procedures are often constrained such that each stage of the process eliminates the minimum degree vertex from the reduced vertex set . Additionally, the vertex elimination procedures are often prohibited the modifying of the adjacency list of the graph’s . Recall from Section 3.2 that vertex elimination data structures must also support the following operations:
Increase_degree increases the degree of vertex by one.
Decrease_degree decreases the degree of vertex by one.
Remove excises vertex from $ .
In_graph determines whether vertex is in .
Minimum_degree finds the vertex in with the smallest degree.
Subsequent sections of this document examine the implementation of these operations.