Please use this identifier to cite or link to this item:
https://elib.bsu.by/handle/123456789/52595| Title: | Computation of the vertex covering number of a graph, each block of which is a complete graph or a complete bipartite graph or a wheel or a power of a cycle or a power of a path |
| Authors: | Lepin, V. V. Talmaciu, M. Duginov, O. I. |
| Keywords: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| Issue Date: | 2013 |
| Publisher: | Минск, БГУ |
| Abstract: | We consider the well-known problem of finding the vertex covering number of a graph. It is known that this problem is NP-hard. In this paper, we give an efficient algorithm for finding the vertex covering number for connected graphs whose blocks are either complete graphs or complete bipartite graphs or wheels or powers of cycles or powers of paths. |
| URI: | http://elib.bsu.by/handle/123456789/52595 |
| Appears in Collections: | Секция 9. Теоретическая информатика |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.