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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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 Šuní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
\mathnet{http://mi.mathnet.ru/adm202}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2364059}
\zmath{https://zbmath.org/?q=an:1164.05443}


Linking options:
  • http://mi.mathnet.ru/eng/adm202
  • http://mi.mathnet.ru/eng/adm/y2007/i2/p1

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Algebra and Discrete Mathematics
    Number of views:
    This page:33
    Full text:19
    First page:1

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2017