Note

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

networkx.algorithms.approximation.treewidth.treewidth_min_fill_in

treewidth_min_fill_in(G)[source]

Returns a treewidth decomposition using the Minimum Fill-in heuristic.

The heuristic chooses a node from the graph, where the number of edges added turning the neighbourhood of the chosen node into clique is as small as possible.

Parameters
GNetworkX graph
Returns
Treewidth decomposition(int, Graph) tuple

2-tuple with treewidth and the corresponding decomposed tree.