Experiments on the minimum linear arrangement problem

DOI10.1145/996546.996554zbMath1069.90117OpenAlexW2090995721MaRDI QIDQ5463444

Jordi Petit

Publication date: 4 August 2005

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: http://www.acm.org/jea/2003/PetitMLAP/

zbMATH Keywords

algorithmexperimental analysisminimum linear arrangement problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (19)

Minimum Linear Arrangement of Series-Parallel Graphs ⋮ Branch and bound for the cutwidth minimization problem ⋮ New relationships for multi-neighborhood search for the minimum linear arrangement problem ⋮ A New Lower Bound for the Minimum Linear Arrangement of a Graph ⋮ On linear layout of bicube and construction of optimal incomplete bicube ⋮ Linear nearest neighbor optimization in quantum circuits: a multiobjective perspective ⋮ The single row facility layout problem: state of the art ⋮ On a binary distance model for the minimum linear arrangement problem ⋮ Lower and upper bounds for the linear arrangement problem on interval graphs ⋮ An optimal time algorithm for minimum linear arrangement of chord graphs ⋮ Heuristics for the data arrangement problem on regular trees ⋮ An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem ⋮ Optimal linear arrangements using betweenness variables ⋮ Unnamed Item ⋮ A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem ⋮ Parameterized algorithmics for linear arrangement problems ⋮ Minimum linear arrangement of chord graphs ⋮ A compact quadratic model and linearizations for the minimum linear arrangement problem ⋮ Bounds of the sum of edge lengths in linear arrangements of trees

Uses Software

• Chaco
• Unnamed Item
• Unnamed Item

Cites Work

• Optimization by Simulated Annealing
• Optimal linear labelings and eigenvalues of graphs
• Some simplified NP-complete graph problems
• Path optimization for graph partitioning problems
• QAPLIB - a quadratic assignment problem library
• Generating lower bounds for the linear arrangement problem
• Applications of the crossing number
• Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs
• Approximating Layout Problems on Random Geometric Graphs
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• On Estimating the Largest Eigenvalue with the Lanczos Algorithm
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• TSPLIB—A Traveling Salesman Problem Library
• Single Machine Job Sequencing with Precedence Constraints
• A Minimum Linear Arrangement Algorithm for Undirected Trees
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Optimal Numberings of an $N \times N$ Array
• Optimal Linear Ordering
• Equation of State Calculations by Fast Computing Machines
• Optimal Assignments of Numbers to Vertices
• Approximating layout problems on random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Experiments on the minimum linear arrangement problem