Geodesic
Algorithms for computing the multiclique degree and the biclique degreeof a series-parallel graph
Trudy Instituta matematiki, Tome 18 (2010) no. 2, pp. 60-78 
V. V. Lepin. Algorithms for computing the multiclique degree and the biclique degreeof a series-parallel graph. Trudy Instituta matematiki, Tome 18 (2010) no. 2, pp. 60-78. http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a5/
@article{TIMB_2010_18_2_a5,
     author = {V. V. Lepin},
     title = {Algorithms for computing the multiclique degree and the biclique degreeof a series-parallel graph},
     journal = {Trudy Instituta matematiki},
     pages = {60--78},
     year = {2010},
     volume = {18},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a5/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - Algorithms for computing the multiclique degree and the biclique degreeof a series-parallel graph
JO  - Trudy Instituta matematiki
PY  - 2010
SP  - 60
EP  - 78
VL  - 18
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a5/
LA  - ru
ID  - TIMB_2010_18_2_a5
ER  - 
%0 Journal Article
%A V. V. Lepin
%T Algorithms for computing the multiclique degree and the biclique degreeof a series-parallel graph
%J Trudy Instituta matematiki
%D 2010
%P 60-78
%V 18
%N 2
%U http://geodesic.mathdoc.fr/item/TIMB_2010_18_2_a5/
%G ru
%F TIMB_2010_18_2_a5

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

A multiclique is a complete multipartite subgraph of a graph. A biclique is a complete bipartite 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). Given a multiclique cover $\mathcal{C}$ of $G$ and a vertex $v\in V(G),$ the degree $v$ on $\mathcal{C}$ is $\rho(G,\mathcal{C},v)=|\{H\in\mathcal{C}:v\in H\}|$. The degree of a multiclique cover $\mathcal{C}$ of $G$, denoted by $\rho(G,\mathcal{C})$, is defined to be: $\rho(G,\mathcal{C})=\max\limits_{v\in V(G)}\rho(G,\mathcal{C},v)$. The multiclique degree of $G$, denoted by $\rho(G)$, is the minimum value of $\rho(G,\mathcal{C})$ as $\mathcal{C}$ ranges over all coverings of $G$. Polinomial-time algorithms for computing the multiclique degree and the biclique degree of a (simple) series-parallel graph are given.

[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] Fishburn P.C., Hammer P.L., “Bipartite dimensions and bipartite degrees of graphs”, Discrete Math., 160 (1996), 127–148 | DOI | MR | Zbl

[3] Benzaken C., Boyd S., Hammer P.L., Simeone B., “Adjoints of pure bidirected graphs”, Congr. Numerantium, 39 (1983), 123–144 | MR | Zbl

[4] Crama Y., Hammer P.L., “Recognition of quadratic graphs and adjoints of bidirected graphs”, Ann. N.Y. Academy Sciences, 555 (1989), 140–149 | DOI | MR | Zbl

[5] Hammer P.L., Simeone B., “Quasimonotone Boolean functions and bistellar graphs.”, Ann. Discrete Math., 9 (1980), 107–119 | DOI | MR | Zbl

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

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

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

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

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

[11] Lepin V.V., “Lineinyi algoritm dlya vychisleniya chisla multiklikovogo pokrytiya posledovatelno-parallelnogo grafa”, Trudy Instituta matematiki, 17:1 (2009), 90–102 | Zbl

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