Комбинаторная надежность сетевых гиперграфов

Abstract

В статье теория доминирования распространена на гиперграфы. Доказано, что 1) задача вычисления доминирования в классе (s, t)-гиперграфов ограниченной степени полиномиально разрешима; 2) доминирование циклических (s, t)-гиперграфов равна нулю, в то время как задача вычисления доминирования в классе нестандартных r-циклических (s, t)-гиперграфов является полной при любом фиксированном натуральном r