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

GNetworkX graph

Returns

Treewidth decomposition(int, Graph) tuple

2-tuple with treewidth and the corresponding decomposed tree.