Том 6, серия 1, номер 3, 1999 г., Стр. 71-86

УДК 519.71
А. А. Черняк
Резидуальная надежность $P$-пороговых графов

Аннотация:
Задача вычисления резидуальной надежности (RES-проблема) решена для всех классов $P$-пороговых графов, для которых ранее были получены эффективные структурные характеризации, основанные на декомпозиции этих графов на неразложимые компоненты. В частности, дано конструктивное доказательство существования линейных алгоритмов вычисления резидуальной надежности для псевдодоминантно-пороговых, доминантно-пороговых, матрогенных и матроидальных графов. В то же время доказано, что RES-проблема является $\#P$-полной в классе бирегулярных графов. Этот результат означает $\#P$-полноту RES-проблемы в классах неразложимых бокс-пороговых и псевдопороговых графов.
Ил. 2, библиогр. 14.

Черняк А. А. ¹
1. Белорусский государственный университет,
220141 Минск, Беларусь
е-mail: zhanna_chernyak@usa.net

Статья поступила 11 ноября 1998 г.
Исправленный вариант — 9 марта 1999 г.