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