Geodesic
Graph reduction in the construction of minimal clique cover
Matematičeskie voprosy kriptografii, Tome 3 (2012) no. 3, pp. 105-128 
P. V. Roldugin. Graph reduction in the construction of minimal clique cover. Matematičeskie voprosy kriptografii, Tome 3 (2012) no. 3, pp. 105-128. http://geodesic.mathdoc.fr/item/MVK_2012_3_3_a5/
@article{MVK_2012_3_3_a5,
     author = {P. V. Roldugin},
     title = {Graph reduction in the construction of minimal clique cover},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {105--128},
     year = {2012},
     volume = {3},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2012_3_3_a5/}
}
TY  - JOUR
AU  - P. V. Roldugin
TI  - Graph reduction in the construction of minimal clique cover
JO  - Matematičeskie voprosy kriptografii
PY  - 2012
SP  - 105
EP  - 128
VL  - 3
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MVK_2012_3_3_a5/
LA  - ru
ID  - MVK_2012_3_3_a5
ER  - 
%0 Journal Article
%A P. V. Roldugin
%T Graph reduction in the construction of minimal clique cover
%J Matematičeskie voprosy kriptografii
%D 2012
%P 105-128
%V 3
%N 3
%U http://geodesic.mathdoc.fr/item/MVK_2012_3_3_a5/
%G ru
%F MVK_2012_3_3_a5

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

The problem of construction of a graph coverage with a minimum number of its complete subgraphs (cliques) is considered. We describe classes of subgraphs for which it is possible to reduce the graph coverage problem to the same problem for graphs of smaller orders. We show that these classes are wider than those known before.

[1] Kellerman E., “Determination of keyword conflict”, IBM Tech. Disclosure Bull., 16:2 (1973), 544–546

[2] Cavers M. S., Clique partitions and coverings of graphs, MSc Thesis, Waterloo, Ontario, Canada, 2005

[3] Gramm J., Guo J., Huffner F., Niedermeier R., “Data reduction, exact, and heuristic algorithms for clique cover”, Proc. 8th Workshop on Algor. Eng. and Exper., SIAM, 2006, 86–94 | MR

[4] Kou L. T., Stockmeyer L. J., Wong C. K., “Cliques with regard to keyword conflicts and intersection graphs”, Comm. ACM, 21:2 (1978), 135–139 | DOI | MR | Zbl

[5] Orlin J., “Contentment in graph theory: Covering graphs with cliques”, Indag. Math., 39 (1977), 406–424 | MR

[6] Gyárfás A., “A simple lower bound on edge coverings by cliques”, Discrete Math., 85 (1990), 103–104 | DOI | MR | Zbl

[7] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Per. s angl., Mir, M., 1979 | MR

[8] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, Per. s angl., MTsNMO, M., 1999

[9] Kharari F., Teoriya grafov, Mir, M., 1973 | MR