Optimal linear arrangement of a rectangular grid
The authors prove the following results. Suppose \(m\geq n\geq 2\). Denote by \(F\) the set of all assignments from \(V_{mn}\) onto \(\{1,2,\dots, mn\}\), and for all \(f\in F\) define \(L(f)\) by \[ L(f)= \sum_{\{u,v\}\in E_{mn}}|f(u)- f(v)|. \] For each \(t\in \{1,2,\dots, \lfloor n/2\rfloor\}\) denote by \(f^{(t)}\) the member of \(F\) that is doubly monotonic, complementary, has pattern \(R_t(m,n)\) in the first \(t\) rows of its assignment matrix with horizontal slats in rows \(t\) through \(m-t\). Then \[ \min_{f\in F} L(f)= L(f^{(t^*)})= m(n^2+ n-1)- n- t^*[2(t^*)^2- 6nt^*+ 3n^2+ 3n- 2]/3, \] where \(t^*\) denotes the value of \(t\in \{1,2,\dots, \lfloor n/2\rfloor\}\) that maximizes \(2t^3- 6nt^2+ (3n^2+ 3n- 2)t\).
- Locality and bounding-box quality of two-dimensional space-filling curves
- An optimal algorithm for rectangle placement
- On minimum cuts and the linear arrangement problem
- Exact solution of the 2-dimensional grid arrangement problem
- Distributed balanced partitioning via linear embedding
- The distance orientation problem
- Minimum Linear Arrangement of Series-Parallel Graphs
- Lower and upper bounds for the linear arrangement problem on interval graphs
- Optimal Numberings of an N \times N Array
- A probabilistic algorithm for optimal linear arrangements
This page was built for publication: Optimal linear arrangement of a rectangular grid
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1970706)
