期刊
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC
卷 60, 期 1, 页码 24-41出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jalgor.2004.10.004
关键词
minimum linear arrangement; combinatorial optimization; multilevel computations; graphs; weighted edge contractions; weighted aggregation; coarsening; interpolation; relaxation; simulated annealing
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据