| Article ID: | iaor1992930 |
| Country: | Japan |
| Volume: | J-74A |
| Issue: | 1 |
| Start Page Number: | 72 |
| End Page Number: | 81 |
| Publication Date: | Jan 1991 |
| Journal: | Transactions of the Institute of Electronics, Information and Communication Engineers |
| Authors: | Hayashi Masahiro |
| Keywords: | graphs |
Overall reliability is a very important measure in net-work reliability analysis. However, the problem of evaluating overall reliability is NP-hard and ‘Planar-CF graph’ has been found to be a class that can be evaluated exactly in polynomial time. This paper introduces an evaluation method for Overall reliability that uses dual graph combined with reduction techniques. In this method, the class called ‘Planer-Dual-CF graph’ can also be evaluated exactly in polynomial time. This class is more complex and larger than ‘Planar-CF-graph’. [In Japanese.]