# Examples of Analysis of Branch and Bound Method

I am solving a graph problem, which can be formulated as an integer programme. Based on computer experiments, it seems that the branch and bound method works well. I would like to analyse the running time, and wonder whether there have been other problems where branch and bound method was used and the theoretical bounds on the running time has been established?

On another note, if anyone knows any examples of problems where the range of possible values that a variable in a linear programme can take, I'd also be interested in.

A good example of non-trivial algorithmic analysis of a practical braching algorithm is the vertex cover problem. It can be proven that if the answer is $$k$$, then a simple branching algorithm has time complexity $$O(2^k n)$$. The analysis uses "bounded search tree" technique.