Abstract
In this short note, we prove the time complexity of full-bucket and mini-bucket elimination [1, 2]. In previous papers, when discussing the complexity of these algorithms, only the importance of the exponential contribution was emphasized and the rest of the contributions to the cost were not carefully considered. In this note, we address this fact and provide a non-trivial bound for the non-exponential contribution to the complexity of both algorithms. We demonstrate the result for the Additive Combinatorial Optimization Problem case.