Optimal indexing of the vertices of graphs
HTML articles powered by AMS MathViewer
- by Carl H. FitzGerald PDF
- Math. Comp. 28 (1974), 825-831 Request permission
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
- Alan J. Hoffman, Michael S. Martin, and Donald J. Rose, Complexity bounds for regular finite difference and finite element grids, SIAM J. Numer. Anal. 10 (1973), 364–369. MR 347065, DOI 10.1137/0710033
Additional Information
- © Copyright 1974 American Mathematical Society
- Journal: Math. Comp. 28 (1974), 825-831
- MSC: Primary 05C99
- DOI: https://doi.org/10.1090/S0025-5718-1974-0379289-6
- MathSciNet review: 0379289