Optimal linear arrangement of a rectangular grid
type: Item
instance of: scholarly article
title: Optimal linear arrangement of a rectangular grid
zbMATH Open document ID: 0949.05044
DOI: 10.1016/S0012-365X(99)00173-9
author: Prasad Tetali
author: Peter Fishburn
author: Peter Winkler
published in: Discrete Mathematics
publication date: 2000-12-03T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 94C15
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1420380
zbMATH Keywords: linear arrangement
zbMATH Keywords: rectangular grid
zbMATH Keywords: bandwidth
zbMATH Keywords: assignments
reviewed by: Chunhui Lai
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1420380