Safro, Ilya; Ron, Dorit; Brandt, Achi Graph minimum linear arrangement by multilevel weighted edge contractions. (English) Zbl 1096.68687 J. Algorithms 60, No. 1, 24-41 (2006). Summary: The minimum linear arrangement problem is widely used and studied in many practical and theoretical applications. In this paper we present a linear-time algorithm for the problem inspired by the algebraic multigrid approach which is based on weighted edge contraction rather than simple contraction. Our results turned out to be better than every known result in almost all cases, while the short running time of the algorithm enabled experiments with very large graphs. Cited in 17 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68W05 Nonnumerical algorithms Keywords:minimum linear arrangement; combinatorial optimization; multilevel computations; graphs; weighted edge contractions; weighted aggregation; coarsening; interpolation; relaxation; simulated annealing PDFBibTeX XMLCite \textit{I. Safro} et al., J. Algorithms 60, No. 1, 24--41 (2006; Zbl 1096.68687) Full Text: DOI