Bandwidth of Bipartite Permutation Graphs

摘要

The bandwidth problem is to find a linear layout of vertices in a graph in such way that minimizes the maximum distance between two vertices joined by an edge. The problem has wide applications including sparse matrix computations and molecular biology. However, the problem is NP-complete even for trees. Three polynomial time algorithms for computing the bandwidth of a graph are presented. The first one is a linear time algorithm for a threshold graph, and the second one is a linear time algorithm for a chain graph. They improve the previously known upper bounds to optimal. The last algorithm solves the bandwidth problem for a bipartite permutation graph. This is the first polynomial time algorithm for the graph class. The results give positive answers to some open problems.