Bandwidth of Bipartite Permutation Graphs in Polynomial Time

摘要

We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Prior to our work, polynomial-time algorithms for exact computation of bandwidth were known only for caterpillars of hair length 2, chain graphs, cographs, and interval graphs.