The paper focuses on finding thembest solutions of a combinatorial optimization problem defined over a graphical model (e.g., themmost probable expla- nations for a Bayesian network). We describe elim- m-opt, a new bucket elimination algorithm for solv- ing the m-best task, provide efficient implementa- tion of its defining combination and marginaliza- tion operators, analyze its worst-case performance, and compare it with that of recent related algo- rithms. An extension to the mini-bucket frame- work, yielding a collection of bounds for each of the m-best solutions is discussed and empirically evaluated. We also formulate the m-best task as a regular reasoning task over general graphical mod- els defined axiomatically, which makes all other in- ference algorithms applicable.