dwave_networkx.algorithms.elimination_ordering.min_width_heuristic¶

min_width_heuristic(G)[source]¶

Computes an upper bound on the treewidth of a graph based on the min-width heuristic for the elimination ordering.

Parameters:	G (graph) – A NetworkX graph.
Returns:	treewidth_upper_bound (int) – An upper bound on the treewidth of the graph G. order (list) – An elimination order that induces the treewidth.

References

Based on the algorithm presented in [GD]