Geodesic
A linear algorithm for computing the multiclique cover number of a series-parallel graph
Trudy Instituta matematiki, Tome 17 (2009) no. 1, pp. 90-102.

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

A multiclique is a complete multipartite subgraph of a graph. A multiclique cover of a graph $G$ is a collection of multicliques of $G$ whose edge sets cover the edge set of $G$ (every edge of $G$ belongs to at least one multiclique of the collection). The multiclique cover number, $mc(G)$, of a graph $G$ is the minimum number of multicliques in a multiclique cover of $G$. A linear-time algorithm for computing the multiclique cover number of a (simple) series-parallel graph is given. 
@article{TIMB_2009_17_1_a8,
     author = {V. V. Lepin},
     title = {A linear algorithm for computing the multiclique cover number of a series-parallel graph},
     journal = {Trudy Instituta matematiki},
     pages = {90--102},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2009_17_1_a8/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - A linear algorithm for computing the multiclique cover number of a series-parallel graph
JO  - Trudy Instituta matematiki
PY  - 2009
SP  - 90
EP  - 102
VL  - 17
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2009_17_1_a8/
LA  - ru
ID  - TIMB_2009_17_1_a8
ER  - 
%0 Journal Article
%A V. V. Lepin
%T A linear algorithm for computing the multiclique cover number of a series-parallel graph
%J Trudy Instituta matematiki
%D 2009
%P 90-102
%V 17
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2009_17_1_a8/
%G ru
%F TIMB_2009_17_1_a8
V. V. Lepin. A linear algorithm for computing the multiclique cover number of a series-parallel graph. Trudy Instituta matematiki, Tome 17 (2009) no. 1, pp. 90-102. http://geodesic.mathdoc.fr/item/TIMB_2009_17_1_a8/

[1] Blundo C., De Santis A., Stinson D.R., Vaccaro U., “Graph Decompositions and Secret Sharing Schemes”, J. Cryptology, 8:1 (1995), 39–64 | DOI | MR | Zbl

[2] 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

[3] 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

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

[5] 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

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

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

[8] 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

[9] 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

[10] 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

[11] 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

[12] 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

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

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

[15] Lepin V.V., “Lineinyi algoritm dlya vychisleniya chisla biklikovogo pokrytiya posledovatelno-parallelnogo grafa”, Trudy Instituta matematiki, 16:2 (2008), 63–75 | Zbl