Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Optimal indexing of the vertices of graphs


Author: Carl H. FitzGerald
Journal: Math. Comp. 28 (1974), 825-831
MSC: Primary 05C99
MathSciNet review: 0379289
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The incidence matrices of various graphs are considered. By reordering the points, the bandwidth can be changed. In the cases of rectangular grids in the plane or cubic grids in three dimensions, the exact, minimum values of the bandwidth are determined.

In certain numerical analysis problems, it is of interest to index the vertices of a graph in such a way that the matrix used to represent an associated system of linear equations is as close to diagonal as possible or, equivalently, to index the vertices of a graph in a way that minimizes the width of the band of nonzero terms in the incidence matrix for that graph. The purpose of this note is to present a few methods of determining the minimum possible width in some cases that arise in the numerical solution of Laplace's equation. Of particular interest are the first proof of Theorem 2 which solves the problem for the common square grid and Theorem 3 which answers the problem for the cubic grid.


References [Enhancements On Off] (What's this?)

  • [A] J. Hoffman, M. S. Martin, & D. J. Rose, "Complexity bounds for regular finite difference and finite element grids," S.I.A.M. J. Numer. Anal., v. 10, 1973, pp. 364-369. MR 0347065 (49:11785)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 05C99

Retrieve articles in all journals with MSC: 05C99


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1974-0379289-6
PII: S 0025-5718(1974)0379289-6
Keywords: Bandwidth, incidence matrix, grids
Article copyright: © Copyright 1974 American Mathematical Society