Том 6, серия 1, номер 3, 1999 г., Стр. 71-86
УДК 519.71
А. А. Черняк
Резидуальная надежность $P$-пороговых графов
Аннотация:
Задача вычисления резидуальной надежности (RES-проблема) решена для всех классов $P$-пороговых графов, для которых ранее были получены эффективные структурные характеризации, основанные на декомпозиции этих графов на неразложимые компоненты. В частности, дано конструктивное доказательство существования линейных алгоритмов вычисления резидуальной надежности для псевдодоминантно-пороговых, доминантно-пороговых, матрогенных и матроидальных графов. В то же время доказано, что RES-проблема является $\#P$-полной в классе бирегулярных графов. Этот результат означает
$\#P$-полноту RES-проблемы в классах неразложимых бокс-пороговых и псевдопороговых
графов.
Ил. 2, библиогр. 14.
Черняк А. А. 1
1. Белорусский государственный университет,
220141 Минск, Беларусь
е-mail: zhanna_chernyak@usa.net
Статья поступила 11 ноября 1998 г.
Исправленный вариант — 9 марта 1999 г.
|