Premium
Node partition formula for directed graph reliability
Author(s) -
Buzacott J. A.
Publication year - 1987
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230170207
Subject(s) - modular decomposition , partition (number theory) , directed acyclic graph , mathematics , indifference graph , maximal independent set , node (physics) , graph partition , set (abstract data type) , intersection (aeronautics) , chordal graph , pathwidth , combinatorics , computer science , discrete mathematics , directed graph , graph , 1 planar graph , line graph , structural engineering , engineering , programming language , aerospace engineering
Cut set inclusion and exclusion is a well known reliability evaluation procedure. However, many of the cut set intersection terms cancel so it can be laborious to use. In directed graphs it is shown that the number of noncancelling terms cannot exceed the number of possible ordered partitions of the set of nodes. The resulting node partition formula will still contain cancelling terms when applied to incomplete graphs. An algorithm is developed to determine the set of noncancelling terms and its application illustrated on some special classes of graphs: acyclic graphs and graphs admitting a modular decomposition.