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 neighborhood 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.