Minimum Linear Arrangement - algorithm, implementation, and experiments

This web page summarizes our work on the minimum linear arrangement problem. You can find here links to our paper, an implementation written by Jon Feldman and Zvika Brakerski, and experimental results.

Paper

Reuven Bar-Yehuda, Guy Even, Jon Feldman, and Seffi Naor, Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems, Journal of Graph Algorithms and Applications

Related Links

• Jordi Petit i Silvestre has collected benchmark graphs and ran many heuristics on them. He has organized everything in a web page titled Experiments on the MinLA Problem.
• Our implementation is based on HMETIS - a graph partitioning package.

Program

The program is writttten in C. A gzipped tar file with the sources and a short readme.

Doug Rogers sent me the following errata.

Results

All the results in a tar file

• The computed permutations.
• Printouts of the Decompose & Orient step and the Heuristic Improvement Step.
• Printout of Petit's simmulated annealing program executed on the best results our orientation algorithm found.

About this document ...