Generating lower bounds for the linear arrangement problem
From MaRDI portal
Publication:1891924
DOI10.1016/0166-218X(93)E0168-XzbMath0827.90136MaRDI QIDQ1891924
Publication date: 13 December 1995
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10)
Related Items (17)
On a class of metrics related to graph layout problems ⋮ A polyhedral approach to the single row facility layout problem ⋮ Exact solution of the 2-dimensional grid arrangement problem ⋮ Decorous combinatorial lower bounds for row layout problems ⋮ 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 ⋮ Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions ⋮ Optimal linear arrangements using betweenness variables ⋮ Unnamed Item ⋮ Single-machine scheduling with an external resource ⋮ Global Approaches for Facility Layout and VLSI Floorplanning ⋮ A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices ⋮ Minimum linear arrangement of chord graphs ⋮ Experiments on the minimum linear arrangement problem ⋮ On minimum cuts and the linear arrangement problem ⋮ A semidefinite optimization approach for the single-row layout problem with unequal dimensions
Cites Work
- On optimal linear arrangements of trees
- Some simplified NP-complete graph problems
- One-dimensional logic gate assignment and interval graphs
- Multi-Terminal Network Flows
- A Minimum Linear Arrangement Algorithm for Undirected Trees
- Optimal Linear Ordering
- An r-Dimensional Quadratic Placement Algorithm
- Optimal Assignments of Numbers to Vertices
This page was built for publication: Generating lower bounds for the linear arrangement problem
