Geodesic
A Multilevel Algorithm for the Minimum 2-sum Problem
Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 237-258.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2006_10_2_a6,
     author = {Ilya Safro and Dorit Ron and Achi Brandt},
     title = {A {Multilevel} {Algorithm} for the {Minimum} 2-sum {Problem}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {237--258},
     publisher = {mathdoc},
     volume = {10},
     number = {2},
     year = {2006},
     doi = {10.7155/jgaa.00126},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00126/}
}
TY  - JOUR
AU  - Ilya Safro
AU  - Dorit Ron
AU  - Achi Brandt
TI  - A Multilevel Algorithm for the Minimum 2-sum Problem
JO  - Journal of Graph Algorithms and Applications
PY  - 2006
SP  - 237
EP  - 258
VL  - 10
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00126/
DO  - 10.7155/jgaa.00126
LA  - en
ID  - JGAA_2006_10_2_a6
ER  - 
%0 Journal Article
%A Ilya Safro
%A Dorit Ron
%A Achi Brandt
%T A Multilevel Algorithm for the Minimum 2-sum Problem
%J Journal of Graph Algorithms and Applications
%D 2006
%P 237-258
%V 10
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00126/
%R 10.7155/jgaa.00126
%G en
%F JGAA_2006_10_2_a6
Ilya Safro; Dorit Ron; Achi Brandt. A Multilevel Algorithm for the Minimum 2-sum Problem. Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 237-258. doi : 10.7155/jgaa.00126. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00126/

Cité par Sources :