On a binary distance model for the minimum linear arrangement problem

DOI10.1007/S11750-012-0263-7MaRDI QIDQ458974zbMATH OpenOpenAlexFDO

Authors Gerhard Reinelt, Hanna Seitz

Publication date 8 October 2014

Published in Top (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11750-012-0263-7

zbMATH Keywords

integer programminggraph layoutlinear arrangement problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Integer programming (90C10)

Recommendations

• A compact quadratic model and linearizations for the minimum linear arrangement problem
• An improved approximation ratio for the minimum linear arrangement problem
• Tractable parameterizations for the minimum linear arrangement problem
• Tractable parameterizations for the minimum linear arrangement problem
• The rectilinear distance minisum problem with minimum distance constraints:
• On minimum cuts and the linear arrangement problem
• scientific article; zbMATH DE number 1617262
• Approximation algorithms for maximum linear arrangement
• A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem
• A branch-and-bound algorithm for the minimum cut linear arrangement problem

Cites work

• scientific article; zbMATH DE number 2084296 (Why is no real title available?)
• scientific article; zbMATH DE number 5605062 (Why is no real title available?)
• scientific article; zbMATH DE number 176780 (Why is no real title available?)
• scientific article; zbMATH DE number 1953102 (Why is no real title available?)
• A Review of the Placement and Quadratic Assignment Problems
• Approximating layout problems on random geometric graphs
• Contributions to the minimum linear arrangement problem.
• Decorous lower bounds for minimum linear arrangement
• Divide-and-conquer approximation algorithms via spreading metrics
• Experiments on the minimum linear arrangement problem
• Generating lower bounds for the linear arrangement problem
• Graph minimum linear arrangement by multilevel weighted edge contractions
• Introduction to ABACUS -- a branch-and-cut system
• Mapping the genome
• Optimal Assignments of Numbers to Vertices
• Optimal Numberings of an $N \times N$ Array
• Optimal linear arrangements using betweenness variables
• Parameterized algorithmics for linear arrangement problems
• SOFSEM 2005: Theory and Practice of Computer Science
• Single Machine Job Sequencing with Precedence Constraints
• The linear arrangement problem parameterized above guaranteed value

Cited in

(5)

• Minimum linear arrangements
• Optimal linear arrangements using betweenness variables
• scientific article; zbMATH DE number 1966611 (Why is no real title available?)
• Contributions to the minimum linear arrangement problem.
• A compact quadratic model and linearizations for the minimum linear arrangement problem

Describes a project that uses

Uses Software

• Harwell-Boeing sparse matrix collection
• CPLEX
• ABACUS

This page was built for publication: On a binary distance model for the minimum linear arrangement problem

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