treewidth_branch_and_bound(G, elimination_order=None, treewidth_upperbound=None)¶
Computes the treewidth of graph G and a corresponding perfect elimination ordering.
Alogorithm based on [GD].
- 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.
- treewidth (int) – The treewidth of graph G.
- order (list) – An elimination order that induces the treewidth.
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])
[GD] Gogate & Dechter, “A Complete Anytime Algorithm for Treewidth”, https://arxiv.org/abs/1207.4109