Exact solution of the 2-dimensional grid arrangement problem

DOI10.1016/j.disopt.2012.07.002zbMath1254.90277OpenAlexW1983889751MaRDI QIDQ1926499

Marcus Oswald, Stefan Wiesberg, Gerhard Reinelt

Publication date: 28 December 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2012.07.002

zbMATH Keywords

polyhedral combinatoricsgeometric embedding2-dimensional grid arrangement

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

An optimal time algorithm for minimum linear arrangement of chord graphs

Uses Software

• KEGG

Cites Work

• Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town?
• A bounded compactness theorem for \(L^ 1\)-embeddability of metric spaces in the plane
• Some simplified NP-complete graph problems
• Generating lower bounds for the linear arrangement problem
• Decorous Lower Bounds for Minimum Linear Arrangement
• Divide-and-conquer approximation algorithms via spreading metrics
• Geometry of cuts and metrics
• Unnamed Item
• Unnamed Item
• Unnamed Item