Skip to main content
`Ctrl`+`K`

# 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.