This article is cited in 6 papers

A linear algorithm for computing the biclique cover number of a series-parallel graph

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus

Abstract: A biclique is a complete bipartite subgraph of a graph. A biclique cover of a graph $G$ is a collection of bicliques of $G$ whose edge sets cover the edge set of $G$ (every edge of $G$ belongs to at least one biclique of the collection). The biclique cover number, $bc(G)$, of a graph $G$ is the minimum number of bicliques in a biclique cover of $G$. The problem of computing $bc(G)$ is NP-hard even for chordal bipartite graphs. A linear-time algorithm for computing the biclique cover number of a (simple) series-parallel graph is given.

UDC: 519.1

Received: 30.05.2008

Bibliographic databases:

•