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_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:G (NetworkX graph)
Returns:Treewidth decomposition – 2-tuple with treewidth and the corresponding decomposed tree.
Return type:(int, Graph) tuple