Geodesic
On optimal exact coverings of a graph in the class of weakly dense bases
Diskretnaya Matematika, Tome 16 (2004) no. 3, pp. 118-140
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider the problem on covering a non-oriented connected graph without loops and multiple edges by graphs of arbitrary finite bases. We introduce the notions of complexity of a covering, complexity of a graph and the Shannon function. In accordance with the asymptotic behaviour of the Shannon function, we introduce two classes of bases, almost dense and weakly dense bases. For the class of weakly dense bases and a special subclass of this class we suggest methods of constructing optimal exact coverings of a graph by bipartite basic graphs and find estimates of the complexity of such coverings. The suggested methods are based on algorithms for optimal exact covering of $(0,1)$-matrices by arbitrary $(0,1)$-matrices and on the connection between coverings of $(0,1)$-matrices and coverings of a graph by bipartite graphs. 
@article{DM_2004_16_3_a6,
     author = {Z. S. Lozhkina},
     title = {On optimal exact coverings of a graph in the class of weakly dense bases},
     journal = {Diskretnaya Matematika},
     pages = {118--140},
     year = {2004},
     volume = {16},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_3_a6/}
}
TY  - JOUR
AU  - Z. S. Lozhkina
TI  - On optimal exact coverings of a graph in the class of weakly dense bases
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 118
EP  - 140
VL  - 16
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_3_a6/
LA  - ru
ID  - DM_2004_16_3_a6
ER  - 
%0 Journal Article
%A Z. S. Lozhkina
%T On optimal exact coverings of a graph in the class of weakly dense bases
%J Diskretnaya Matematika
%D 2004
%P 118-140
%V 16
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2004_16_3_a6/
%G ru
%F DM_2004_16_3_a6
Z. S. Lozhkina. On optimal exact coverings of a graph in the class of weakly dense bases. Diskretnaya Matematika, Tome 16 (2004) no. 3, pp. 118-140. http://geodesic.mathdoc.fr/item/DM_2004_16_3_a6/

[1] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, Moskva, 1990 | MR | Zbl

[2] Lozhkina Z. S., “Matematicheskoe modelirovanie i optimalnoe upravlenie”, Vestnik Nizhegorodskogo Gosuniversiteta, 22, no. 1, 2000

[3] Lozhkina Z. S., “O mnozhestve pochti plotnykh bazisov v klasse grafov”, Vestnik Moskovskogo un-ta. Ser. 15, Vych. matem. i kibern., 2000, no. 3, 45–50 | MR | Zbl

[4] Lozhkina Z. S., “O slabo plotnykh bazisakh v klasse grafov”, Vestnik Moskovskogo un-ta. Ser. 15. Vych. matem. i kibern., 2001, no. 2, 47–53 | MR

[5] Lozhkina Z. S., O slozhnosti pokrytiya grafov grafami iz spetsialnykh bazisov, Dissertatsiya na soiskanie uchenoi stepeni kandidata fiz.-matem. nauk, 2002