dwave_networkx.algorithms.elimination_ordering.min_fill_heuristic#
- min_fill_heuristic(G)[source]#
Computes an upper bound on the treewidth of graph G based on the min-fill heuristic for the elimination ordering.
- Parameters:
G (NetworkX graph) – The graph on which to compute an upper bound for the treewidth.
- Returns:
treewidth_upper_bound (int) – An upper bound on the treewidth of the graph G.
order (list) – An elimination order that induces the treewidth.
Examples
This example computes an upper bound for the treewidth of the \(K_4\) complete graph.
>>> K_4 = nx.complete_graph(4) >>> tw, order = dnx.min_fill_heuristic(K_4)
References
Based on the algorithm presented in [GD]