Резидуальная надежность $P$-пороговых графов

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