dwave_networkx.algorithms.elimination_ordering.minor_min_width

minor_min_width(G)

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]