# 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.

Alogorithm 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

GD

Gogate & Dechter, “A Complete Anytime Algorithm for Treewidth”, https://arxiv.org/abs/1207.4109