- 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.
Gis a NetworkX graph.
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.