Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.approximation.treewidth.treewidth_min_degree

treewidth_min_degree(G)

Returns a treewidth decomposition using the Minimum Degree heuristic.

The heuristic chooses the nodes according to their degree, i.e., first the node with the lowest degree is chosen, then the graph is updated and the corresponding node is removed. Next, a new node with the lowest degree is chosen, and so on.

Parameters:G (NetworkX graph) Returns:Treewidth decomposition – 2-tuple with treewidth and the corresponding decomposed tree. Return type:(int, Graph) tuple