Algorithms for finding biclique covers of graphs with bounded pathwidth

In this paper we present space-efficient algorithms for solving construction variants of biclique cover problems on graphs with bounded pathwidth. A biclique is a complete bipartite subgraph of a graph. Algorithms for solving the problem of finding a biclique cover with minimal degree and the problem of finding a biclique cover with minimal number of bicliques on this type of graphs in $O(n\log n)$ time with $O(\log n)$ additional memory are given.