A Multilevel Algorithm for the Minimum 2-sum Problem
Ilya Safro, Dorit Ron, and Achi Brandt
Vol. 10, no. 2, pp. 237-258, 2006. Regular paper.
Abstract In this paper we introduce a direct motivation for solving the minimum 2-sum problem, for which we present a linear-time algorithm inspired by the Algebraic Multigrid
approach which is based on weighted edge contraction. Our results turned out to be better than previous results, while the short running time of the
algorithm enabled experiments with very large graphs. We thus introduce a new benchmark for the minimum 2-sum problem which contains 66 graphs of various characteristics. In addition, we propose the straightforward use of a part of our algorithm as a powerful local reordering method for any other (than multilevel) framework.
Submitted: October 2004.
Revised: March 2006.
Communicated by Ernst W. Mayr
article (PDF)