Bipartite permutation graphs with application to the minimum buffer size problem Original Research Article

This paper presents a new characterization of bipartite permutation graphs and a structure theorem for (0, 1)-matrices with a special consecutive 1ʹs property. These results lead to a lineartime algorithm for the minimum buffer size problem when restricted to bipartite permutation graphs; this problem arises in relational database systems and is NP-hard for a general graph.