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/

[1] Amilhastre J., Janssen P., Vilarem M.-C., “Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs”, Disc. App. Math., 86 (1998), 125–144 | DOI | MR | Zbl

[2] Günlük O., “A new min-cut max-flow ratio for multicommodity flows”, SIAM Journal on Discrete Mathematics, 21:1 (2007), 1–15 | DOI | MR

[3] Fishburn P.C., Hammer P.L., “Bipartite dimensions and bipartite degrees of graphs”, Discrete Math., 160 (1996), 127–148 | DOI | MR | Zbl

[4] Monson S.D., Pullman N.J., Rees R., “A survey of clique and biclique coverings and factorizations of $(0,1)$-matrices”, Bulletin of the ICA, 14 (1995), 17–86 | MR | Zbl

[5] Orlin J., “Contentment in Graph Theory”, Indag. Math., 39 (1977), 758–762 | MR

[6] Muller H., “On edge perfectness and classes of bipartite graphs”, Discrete Math., 149 (1996), 159–187 | DOI | MR

[7] Fleischner H., Mujuni E., Paulusma D., Szeider S., “Covering Graphs with Few Complete Bipartite Subgraphs”, Proceedings of FSTTCS 2007, the 27th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, 4855, 2007, 340–351 | MR | Zbl

[8] Bern M.W., Lawler E.L., Wong A.L., “Linear time computation of optimal subgraphs of decomposable graphs”, J. Algorithms, 8 (1987), 216–235 | DOI | MR | Zbl

[9] Borie R.B., Parker R.G., Tovey C.A., “Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families”, Algorithmica, 7 (1992), 555–581 | DOI | MR | Zbl

[10] Kikuno T., Yoshida N., Kakuda Y., “A linear algorithm for the domination number of a series-parallel graph”, Disc. Appl. Math., 5 (1983), 299–311 | DOI | MR | Zbl

[11] Takamizawa K., Nishizeki T., Saito N., “Linear-time computability of combinatorial problems on series-parallel graphs”, J. ACM, 29 (1982), 623–641 | DOI | MR | Zbl

[12] Duffin R.J., “Topology of series-parallel graphs”, J. Math. Anal. Appl., 10 (1965), 303–318 | DOI | MR | Zbl

[13] Valdes J., Tarjan R.E., Lawler E.L., “The recognition of series parallel digraphs”, SIAM J. Comput., 11 (1982), 298–313 | DOI | MR | Zbl