Расщепляемые графы в задачах покрытия
| dc.contributor.author | Черняк, Аркадий Александрович | |
| dc.date.accessioned | 2020-10-05T08:08:14Z | |
| dc.date.available | 2020-10-05T08:08:14Z | |
| dc.date.issued | 1998 | |
| dc.description.abstract | The # P-completeness of reliability covering problem (RCP) is proved in the class of split graphs that are trees. Boundary conditions for a set of routes that give a criterion for polynomial solvability of the RCP are found for arbitrary trees. As a corollary, the subclass of trees with a set of routes being split graphs, in which the RCP is polynomially solvable, is characterized. The split dimension of trees is shown to be determined in linear time. | |
| dc.identifier.uri | http://elib.bspu.by/handle/doc/48563 | |
| dc.relation.ispartofseries | Весці Нацыянальнай акадэміі навук Беларусі, Серыя фізіка-матэматычных навук; № 2.- С. 131-136 | |
| dc.subject | теория графов | ru_RU |
| dc.subject | расщепляемые графы | ru_RU |
| dc.title | Расщепляемые графы в задачах покрытия | ru_RU |