АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ ГРАФОВЫХ ЗАДАЧ НАДЕЖНОСТИ

Abstract

It is known that the problem of computing the all-terminal reliability is #.P-complete for planar graphs while being polynomially solvable for trees, series-parallel graphs and complete graphs. In this paper it is proved that the problem of computing all-terminal reliability is #P-complete for bipartite graphs of arbitrary girth and for split graphs with the regular part of degree 2.