1.2.2 Bandwidth Reduction
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.
Implementations
Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 9)
Stony Brook Project Implementations (C++) (rating 6)
Related Problems
Feedback Edge/Vertex Set
Solving Linear Equations
Topological Sorting
Go to the corresponding chapter in the book
About the Book
Send us Mail
Go to Main Page
This page last modified on Tue Jun 03, 1997
.