dwave_networkx.algorithms.elimination_ordering.minor_min_width¶

minor_min_width(G)[source]

Computes a lower bound for the treewidth of graph G.

Parameters

G (NetworkX graph) – The graph on which to compute a lower bound on the treewidth.

Returns

lb – A lower bound on the treewidth.

Return type

int

Examples

This example computes a lower bound for the treewidth of the $$K_7$$ complete graph.

>>> K_7 = nx.complete_graph(7)
>>> dnx.minor_min_width(K_7)
6


References

Based on the algorithm presented in [GD]