Перевод названия: Software for the analysis of technical systems fault tolerance based on the graph vertex integrity
Тип публикации: статья из журнала
Год издания: 2015
Ключевые слова: отказоустойчивость систем, графовые модели систем, алгоритмы на графах, вершинная целостность графа, минимальный сепаратор
Аннотация: В настоящее время в связи с применением графовых моделей при проектировании отказоустойчивых сложных технических систем особое внимание уделяется исследованию мер целостности графов. Вершинная целостность – одна из детерминированных мер целостности графа. Система считается полностью работоспособной, если соответствующий ей граф свяПоказать полностьюзный. Вершинная целостность позволяет оценить частичную потерю работоспособности системы вследствие отказа ее элементов. Вершинной целостностью графа G = (V, E) называется величина I(G) = = min S ? V {| S | + w(G – S)}, где w(G – S) – порядок наибольшей компоненты связности графа G – S, который получа-ется из G удалением всех вершин, входящих в S. Значение w(G – S) характеризует размер самого крупного фрагмента системы, образованного после выхода из строя сразу всех элементов из S. Понятие вершинной целостности графа введено Багга, Барфутом, Энтрингером и Свортом. Известно, что задача вычисления I(G) для графа общего вида является NP-трудной. Для нахождения точного значения вершинной целостности необходимо знание всех сепараторов графа. В работе представлены алгоритм и программные средства нахождения приближенного значения I(G). Предлагаемый алгоритм ограничивается рассмотрением всех минимальных сепараторов, поэтому дает лишь верхнюю оценку вершинной целостности. Трудоемкость алгоритма полиномиально зависит от числа вершин и числа минимальных сепараторов входного графа. Результаты экспериментов показали, что вычисленные оценки являются хорошими и часто достижимыми. При выполнении вычислительных экспериментов точное значение вершинной целостности определялось с помощью исчерпывающего перебора всех сепараторов входного графа. Nowadays the study of graphs integrity measures is of current interest due to the use of graph models in the design of fault-tolerant complex technical systems. Vertex integrity is one of the determined measures of graph integrity. The system is considered to be ful-ly operational if the corresponding graph is connected. The vertex integrity evaluates the partial loss of system performance due to the com-ponent failure. The graph vertex integrity G = (V, E) is a value of I(G) = min S ? V {| S | + w(G – S)}, where w(G – S) is the order of the highest component of the graph connectivity G – S, which is obtained from G by removing all elements belonging to S. The value of w(G – S) char-acterizes the size of the largest fragment of the system, which was formed after the failure of all elements of S. The definition of a vertex in-tegrity of a graph was introduced by Bagga, Barefoot, Entringer and Swart. It is known that the problem of computing I(G) for a general graph is NP-hard. To find the exact value of the vertex integrity we have to know all separators of the graph. This paper presents an algo-rithm and software for finding an approximate value of I(G). The proposed algorithm is limited by considering all minimal separators, there-fore it gives only an upper bound of the vertex integrity. The algorithm labor intensivity polynomially depends on the number of vertices and minimal separators of the input graph. The experimental results showed that the calculated estimates are good and often achievable. When carrying out computational experiments, the exact value of the vertex integrity was received by an exhaustive search of all separators of the input graph.
Журнал: Программные продукты и системы
Выпуск журнала: № 3
Номера страниц: 161-165
ISSN журнала: 0236235X
Место издания: Тверь
Издатель: Закрытое акционерное общество Научно-исследовательский институт Центрпрограммсистем