QuickBB
QuickBB is a complete and anytime algorithm for computing the treewidth of a graph.
Author
Description
QuickBB is a complete and anytime algorithm for computing the treewidth of a graph. When given enough time, it yields the exact treewidth of the graph. When stopped before termination, it yields an upper bound on the treewidth.
Input format
The belief network has to be specified in the .cnf format or .cg format
Usage
The algorithm is invoked with the following command line arguments:
quickbb [option1] [option2] --cnffile CNFFILE
Parameters
Parameters for the algorithm, which can be specified within the parameter file:
--random ordering: Branching performed using a randomly selected ordering
--min-fill-ordering: Branching performed using the min-fill ordering
--time <int> : Run the program until the specified time.
--lb: compute a lower bound on the treewidth and exit.
--outfile <out> : Store the treewidth, lb and the perfect-elimination order in the specified output file
Download
A 32-bit Linux binary and an example parameter file is available here.
A 64-bit Linux binary and an example parameter file is available here.
If you are interested in obtaining the source code, please contact the program author.
References
Vibhav Gogate and Rina Dechter A complete Anytime Algorithm for treewidth , In UAI 2004. Link