Geodesic
A linear algorithm for computing the biclique cover number of a series-parallel graph
Trudy Instituta matematiki, Tome 16 (2008) no. 2, pp. 63-75

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{TIMB_2008_16_2_a6,
     author = {V. V. Lepin},
     title = {A linear algorithm for computing the biclique cover number of a series-parallel graph},
     journal = {Trudy Instituta matematiki},
     pages = {63--75},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2008_16_2_a6/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - A linear algorithm for computing the biclique cover number of a series-parallel graph
JO  - Trudy Instituta matematiki
PY  - 2008
SP  - 63
EP  - 75
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2008_16_2_a6/
LA  - ru
ID  - TIMB_2008_16_2_a6
ER  - 
%0 Journal Article
%A V. V. Lepin
%T A linear algorithm for computing the biclique cover number of a series-parallel graph
%J Trudy Instituta matematiki
%D 2008
%P 63-75
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2008_16_2_a6/
%G ru
%F TIMB_2008_16_2_a6
V. V. Lepin. A linear algorithm for computing the biclique cover number of a series-parallel graph. Trudy Instituta matematiki, Tome 16 (2008) no. 2, pp. 63-75. http://geodesic.mathdoc.fr/item/TIMB_2008_16_2_a6/