  This paper extends the work in [Suzuki, 1996] and presents an efficient
depth-first branch-and-bound algorithm for learning Bayesian network
structures, based on the minimum description length (MDL) principle, for a
given (consistent) variable ordering. The algorithm exhaustively searches
through all network structures and guarantees to find the network with the best
MDL score. Preliminary experiments show that the algorithm is efficient, and
that the time complexity grows slowly with the sample size. The algorithm is
useful for empirically studying both the performance of suboptimal heuristic
search algorithms and the adequacy of the MDL principle in learning Bayesian
networks.
