dwave_networkx.algorithms.elimination_ordering.treewidth_branch_and_bound#

treewidth_branch_and_bound(G, elimination_order=None, treewidth_upperbound=None)[source]#

Computes the treewidth of graph G and a corresponding perfect elimination ordering.

Algorithm based on [GD].

Parameters:

  • G (NetworkX graph) – The graph on which to compute the treewidth and perfect elimination ordering.

  • elimination_order (list (optional, Default None)) – An elimination order used as an initial best-known order. If a good order is provided, it may speed up computation. If not provided, the initial order is generated using the min-fill heuristic.

  • treewidth_upperbound (int (optional, Default None)) – An upper bound on the treewidth. Note that using this parameter can result in no returned order.

Returns:

  • treewidth (int) – The treewidth of graph G.

  • order (list) – An elimination order that induces the treewidth.

Examples

This example computes the treewidth for the \(K_7\) complete graph using an optionally provided elimination order (a sequential ordering of the nodes, arbitrally chosen).

>>> K_7 = nx.complete_graph(7)
>>> dnx.treewidth_branch_and_bound(K_7, [0, 1, 2, 3, 4, 5, 6])
(6, [0, 1, 2, 3, 4, 5, 6])

References

Based on the algorithm presented in [GD]