strategy_smallest_last

strategy_smallest_last(G, colors)

Returns a deque of the nodes of G, “smallest” last.

Specifically, the degrees of each node are tracked in a bucket queue. From this, the node of minimum degree is repeatedly popped from the graph, updating its neighbors’ degrees.

G is a NetworkX graph. colors is ignored.

This implementation of the strategy runs in \(O(n + m)\) time (ignoring polylogarithmic factors), where \(n\) is the number of nodes and \(m\) is the number of edges.

This strategy is related to strategy_independent_set(): if we interpret each node removed as an independent set of size one, then this strategy chooses an independent set of size one instead of a maximal independent set.