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.
Branch-and-bound is a heuristic.  In this context, my impression is that typically analysis of the worst-case running time of such heuristics is not enlightening: the worst-case running time is typically exponential.  On some problems in practice branch-and-bound may run significantly faster than that, but my sense is that worst-case running time analysis usually isn't very helpful for predicting when that will happen.