Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

networkx.algorithms.approximation.treewidth.treewidth_min_degree

treewidth_min_degree(G)[source]

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.