Affordable Access

Publisher Website

Enumeration of minimal cutsets of an undirected graph

Authors
Journal
Microelectronics Reliability
0026-2714
Publisher
Elsevier
Publication Date
Volume
30
Issue
1
Identifiers
DOI: 10.1016/0026-2714(90)90006-9
Disciplines
  • Computer Science
  • Design
  • Mathematics

Abstract

Abstract Cutsets and tiesets are needed to calculate reliability of or maximal flow through a network. Algorithms for enumeration of these cutsets and tiesets are being designed to facilitate these calculations. However, these algorithms either involve advanced mathematics or are based on technical notions and ideas such as fault tree analysis, etc. We have given here two different algorithms for enumerating minimal cutsets of an undirected graph (i.e. with feedback). An algorithm, proposed to enumerate minimal cutsets of an acyclic directed graph with adjacent nodes, is also shown to hold for an undirected one with some modifications; the second one is for finding minimal cutsets of a general undirected graph, which holds good for a directed one as well. Our algorithms are simple and do not need any prior knowledge of reliability notions or ideas, or advanced mathematics. Three examples are given to illustrate the algorithms.

There are no comments yet on this publication. Be the first to share your thoughts.