RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Algebra Discrete Math.: Year: Volume: Issue: Page: Find

 Algebra Discrete Math., 2007, Issue 2, Pages 1–15 (Mi adm202)

RESEARCH ARTICLE

Bandwidth reduction in rectangular grids

Titu Andreescua, Water Stromquistb, Zoran Šunícc

a Mathematical Sciences, The University of Texas at Dallas, Richardson, TX 75083–0688, USA
b Swarthmore College, Department of Mathematics and Statistics, 500 College Avenue, Swarthmore, PA. 19081, USA
c Department of Mathematics, Texas A&M University, MS–3368, College Station, TX 77843–3368, USA

Abstract: We show that the bandwidth of a square two-dimensional grid of arbitrary size can be reduced if two (but not less than two) edges are deleted. The two deleted edges may not be chosen arbitrarily, but they may be chosen to share a common endpoint or to be non-adjacent.
We also show that the bandwidth of the rectangular $n \times m$ ($n\leq m$) grid can be reduced by $k$, for all $k$ that are sufficiently small, if $m-n+2k$ edges are deleted.

Keywords: linear bandwidth, rectangular grid.

Full text: PDF file (542 kB)

Bibliographic databases:

Document Type: Article
MSC: 05C78
Language: English

Citation: Titu Andreescu, Water Stromquist, Zoran Šuníc, “Bandwidth reduction in rectangular grids”, Algebra Discrete Math., 2007, no. 2, 1–15

Citation in format AMSBIB
\Bibitem{AndStrSun07}
\by Titu~Andreescu, Water~Stromquist, Zoran~{\v S}un{\'\i}c
\paper Bandwidth reduction in rectangular grids
\jour Algebra Discrete Math.
\yr 2007
\issue 2
\pages 1--15
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2364059}
\zmath{https://zbmath.org/?q=an:1164.05443}