The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.2.2 Bandwidth Reduction

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A graph G=(V,E), representing an n x n matrix M of zero and non-zero elements.

Problem: Which permutation p of the vertices of V minimizes \max_{(i,j) \in E} |p(i) - p(j)|, or equivalently the length of the longest edge when the vertices are ordered on a line.

Excerpt from The Algorithm Design Manual: Bandwidth reduction lurks as a hidden but important problem for both graphs and matrices, and it is important to see how it arises so as to properly recognize it. Applied to matrices, it permutes the rows and columns of a sparse matrix so as to minimize the distance b of any nonzero entry from the center diagonal. This is important in solving linear systems, because Gaussian elimination can be performed in O(n b2) on matrices of bandwidth b. This is a big win over the general O(n3) algorithm if b << n.

Bandwidth minimization on graphs arises in more subtle ways. Arranging a set of n circuit components in a line on a circuit board so as to minimize the length of the longest wire (and hence time delay) is a bandwidth problem, where each vertex of our graph corresponds to a circuit component and there is an edge for every wire linking two components.


Implementations

  • Finding Exact Solutions to the Bandwidth Minimization Problem (C) (rating 9)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 8)
  • Minimum Linear Arrangment programs (C++) (rating 8)
  • The Bandwidth Problem (C) (rating 8)
  • Stony Brook Project Implementations (C++) (rating 5)

  • Recommended Books

  • None Available

    Related Problems


      
    Feedback Edge/Vertex Set
      
    Solving Linear Equations
      
    Topological Sorting



    This page last modified on 2008-07-10 .
    www.algorist.com