Graph minimum linear arrangement by multilevel weighted edge contractions

DOI10.1016/J.JALGOR.2004.10.004MaRDI QIDQ5483510zbMATH OpenOpenAlexFDO

Authors Ilya Safro, Dorit Ron, 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

coarseningcombinatorial optimizationgraphsinterpolationminimum linear arrangementmultilevel computationsrelaxationsimulated annealingweighted aggregationweighted edge contractions

Mathematics Subject Classification ID

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

Recommendations

• Multilevel algorithms for linear ordering problems
• A Multilevel Algorithm for the Minimum 2-sum Problem
• scientific article; zbMATH DE number 1953102
• Experiments on the minimum linear arrangement problem
• Contributions to the minimum linear arrangement problem.

Cited in

(21)

• Fast simulated annealing for single-row equidistant facility layout
• New relationships for multi-neighborhood search for the minimum linear arrangement problem
• Multilevel graph partitioning for three-dimensional discrete fracture network flow simulations
• An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem
• Continuous quadratic programming formulations of optimization problems on graphs
• Maximum incomplete recursive circulants in graph embeddings
• Advanced coarsening schemes for graph partitioning
• A New Lower Bound for the Minimum Linear Arrangement of a Graph
• Summarizing transactional databases with overlapped hyperrectangles
• scientific article; zbMATH DE number 1953102 (Why is no real title available?)
• On a binary distance model for the minimum linear arrangement problem
• Approximation guarantees for the minimum linear arrangement problem by higher eigenvalues
• An optimal time algorithm for minimum linear arrangement of chord graphs
• ELRUNA: elimination rule-based network alignment
• Aggregative coarsening for multilevel hypergraph partitioning
• Relaxation-based coarsening for multilevel hypergraph partitioning
• A Multilevel Algorithm for the Minimum 2-sum Problem
• Multilevel algorithms for linear ordering problems
• Multiscale approach for the network compression-friendly ordering
• A multilevel bilinear programming algorithm for the vertex separator problem
• A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem

This page was built for publication: Graph minimum linear arrangement by multilevel weighted edge contractions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5483510)