A Branch-and-Bound Algorithm for Pagination

The paper presents an algorithm for partitioning the nodes of a weighted graph in order to minimize the interset weights. The algorithm is patterned after the branch-and-probabilistic-bound procedures of Graves and Whinston. Final partitions or solutions are characterized by probability statements like: “the probability is greater than α that a randomly selected solution is inferior to the final.” The algorithm can be used to segment computer programs and data libraries when statistics on the transition or reference rates among program or data elements are known. Numerical results demonstrate the feasibility of efficiently partitioning 50-node graphs.