caa a22 4500 378930451 CHVBK 20180305123628.0 cr unu---uuuuu 161128e20040801xx s 000 0 eng 10.1515/1569392041938776 doi (NATIONALLICENCE)gruyter-10.1515/1569392041938776 Lozhkina Z. S. On optimal exact coverings of a graph in the class of weakly dense bases [Elektronische Daten] [Z. S. Lozhkina] 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. Copyright 2004, Walter de Gruyter Discrete Mathematics and Applications Walter de Gruyter 14/4(2004-08-01), 385-407 0924-9265 14:4<385 2004 14 dma https://doi.org/10.1515/1569392041938776 text/html Onlinezugriff via DOI 1 research article jats NATIONALLICENCE 856 40 https://doi.org/10.1515/1569392041938776 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Lozhkina Z. S. NATIONALLICENCE 773 0- Discrete Mathematics and Applications Walter de Gruyter 14/4(2004-08-01), 385-407 0924-9265 14:4<385 2004 14 dma CC0 http://creativecommons.org/publicdomain/zero/1.0 nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-gruyter