dwave_networkx.algorithms.elimination_ordering.max_cardinality_heuristic#

max_cardinality_heuristic(G)[source]#

Computes an upper bound on the treewidth of graph G based on the max-cardinality 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.max_cardinality_heuristic(K_4)

References

Based on the algorithm presented in [GD]