Journal
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC
Volume 60, Issue 1, Pages 24-41Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jalgor.2004.10.004
Keywords
minimum linear arrangement; combinatorial optimization; multilevel computations; graphs; weighted edge contractions; weighted aggregation; coarsening; interpolation; relaxation; simulated annealing
Ask authors/readers for more resources
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. (c) 2004 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available