Generating lower bounds for the linear arrangement problem

DOI10.1016/0166-218X(93)E0168-XMaRDI QIDQ1891924zbMATH OpenFDO

Authors Weiguo Liu, Anthony Vannelli

Publication date 13 December 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(93)E0168-X

zbMATH Keywords

linear arrangementminimum cuts algorithmrank constraints

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Linear programming (90C05) Programming involving graphs or networks (90C35)

Recommendations

• A New Lower Bound for the Minimum Linear Arrangement of a Graph
• Lower bounds for the minimum linear arrangement of a graph
• Decorous lower bounds for minimum linear arrangement
• Linear Arrangement Problems and Interval Graphs
• Experiments on the minimum linear arrangement problem

Cites work

• A Minimum Linear Arrangement Algorithm for Undirected Trees
• An r-Dimensional Quadratic Placement Algorithm
• Multi-Terminal Network Flows
• On optimal linear arrangements of trees
• One-dimensional logic gate assignment and interval graphs
• Optimal Assignments of Numbers to Vertices
• Optimal Linear Ordering
• Some simplified NP-complete graph problems

Cited in

(17)

• On minimum cuts and the linear arrangement problem
• Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions
• Optimal linear arrangements using betweenness variables
• Exact solution of the 2-dimensional grid arrangement problem
• Single-machine scheduling with an external resource
• Decorous combinatorial lower bounds for row layout problems
• A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices
• Minimum linear arrangement of chord graphs
• A semidefinite optimization approach for the single-row layout problem with unequal dimensions
• Global approaches for facility layout and VLSI floorplanning
• Lower bounds for the minimum linear arrangement of a graph
• A polyhedral approach to the single row facility layout problem
• 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
• Experiments on the minimum linear arrangement problem
• On a class of metrics related to graph layout problems

This page was built for publication: Generating lower bounds for the linear arrangement problem

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