General data structure and algorithms for branch and bound search
Jigang Wu · 2002
We present a data structure called cubeheap and related algorithms for processing OPEN list in branch and bound search. The complexity of the old search algorithm O(mlogm) is reduced to O(m+klogmax {k,r}) especially to O(m+logmloglogm) in an average case, and this data structure and related algorithms are general for branch and bound searches. m is the number of created nodes, k is the number of expanded nodes and r is the branch number of some node which is in most branches.