×

Graph minimum linear arrangement by multilevel weighted edge contractions. (English) Zbl 1096.68687

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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI