Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elib.bspu.by/handle/doc/47841Полная запись метаданных
| Поле DC | Значение | Язык |
|---|---|---|
| dc.contributor.author | Черняк, Аркадий Александрович | - |
| dc.date.accessioned | 2020-05-04T09:31:02Z | - |
| dc.date.available | 2020-05-04T09:31:02Z | - |
| dc.date.issued | 1998 | - |
| dc.identifier.uri | http://elib.bspu.by/handle/doc/47841 | - |
| dc.description.abstract | The problem of computing domination is proved to be NP-hard even restricted to acyclic monotone graphs with the number of cutsets (pathsets) quadratically depending on the graph dimension. The similar problem for acyclic monotone graphs of the fixed degree is shown to be polynomially solvable. It is also proved that the problem of computing reliability is NP-hard even restricted to the class of dc-trivial monotone graph of degree 2 in which the number of cutsets (pathsets) linearly depends on the graph dimension. | - |
| dc.relation.ispartofseries | Весці Нацыянальнай акадэміі навук Беларусі. Серыя фізіка-тэхнічных навук. №3; | - |
| dc.subject | теория графов | ru_RU |
| dc.subject | ациклический монотонный граф | ru_RU |
| dc.title | Ациклические монотонные графы: доминирование и надежность | ru_RU |
| Располагается в коллекциях: | Научные публикации физико-математического факультета | |
Файлы этого ресурса:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 4.pdf | 3,53 MB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.