Graph minimum linear arrangement by multilevel weighted edge contractions

DOI10.1016/J.JALGOR.2004.10.004MaRDI QIDQ5483510zbMATHOpenAlexFDO

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

simulated annealinggraphsinterpolationcombinatorial optimizationcoarseningrelaxationweighted aggregationminimum linear arrangementweighted edge contractionsmultilevel computations

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)

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

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)