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 Algorithms¹¹https://vismor.com/documents/network_analysis/matrix_algorithms/ require an efficient vertex elimination model that supports the sequential elimination of all vertices $V(G)$ from the graph $G=(V,E)$. The procedures are often constrained such that each stage of the process eliminates the minimum degree vertex $v$ from the reduced vertex set $V^{{\prime}}(G^{{\prime}})$. Additionally, the vertex elimination procedures are often prohibited the modifying of the adjacency list of the graph’s $A(G)$. Recall from Section 3.2 that vertex elimination data structures must also support the following operations:

• Increase_degree increases the degree of vertex $v$ by one.

• Decrease_degree decreases the degree of vertex $v$ by one.

• Remove excises vertex $v$ from $$V^{\prime}(G^{\prime})$ .

• In_graph determines whether vertex $v$ is in $V^{\prime}(G^{\prime})$.

• Minimum_degree finds the vertex $v$ in $V^{{\prime}}(G^{{\prime}})$ with the smallest degree.

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