strategy_smallest_last¶
- strategy_smallest_last(G, colors)[source]¶
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.