Graph minimum linear arrangement by multilevel weighted edge contractions

DOI10.1016/j.jalgor.2004.10.004zbMath1096.68687OpenAlexW2049820532MaRDI QIDQ5483510

Dorit Ron, Ilya Safro, Achi Brandt

Publication date: 14 August 2006

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.10.004

zbMATH Keywords

interpolationcombinatorial optimizationsimulated annealingrelaxationgraphscoarseningweighted aggregationminimum linear arrangementweighted edge contractionsmultilevel computations

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Continuous quadratic programming formulations of optimization problems on graphs, Fast simulated annealing for single-row equidistant facility layout, New relationships for multi-neighborhood search for the minimum linear arrangement problem, ELRUNA, A New Lower Bound for the Minimum Linear Arrangement of a Graph, Summarizing transactional databases with overlapped hyperrectangles, On a binary distance model for the minimum linear arrangement problem, An optimal time algorithm for minimum linear arrangement of chord graphs, A multilevel bilinear programming algorithm for the vertex separator problem, An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem, Multiscale approach for the network compression-friendly ordering, Maximum incomplete recursive circulants in graph embeddings, Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning, A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem, Advanced Coarsening Schemes for Graph Partitioning, Multilevel graph partitioning for three-dimensional discrete fracture network flow simulations, Unnamed Item