Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elib.bspu.by/handle/doc/47841| Название: | Ациклические монотонные графы: доминирование и надежность |
| Авторы: | Черняк, Аркадий Александрович |
| Ключевые слова: | теория графов ациклический монотонный граф |
| Дата публикации: | 1998 |
| Серия/номер: | Весці Нацыянальнай акадэміі навук Беларусі. Серыя фізіка-тэхнічных навук. №3; |
| Краткий осмотр (реферат): | 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. |
| URI (Унифицированный идентификатор ресурса): | http://elib.bspu.by/handle/doc/47841 |
| Располагается в коллекциях: | Научные публикации физико-математического факультета |
Файлы этого ресурса:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 4.pdf | 3,53 MB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.