Simple enumeration of minimal cutsets in a class of planar graphs

Abstract

This thesis considers three problems concerned with enumerating all the minimal cutsets disconnecting a set of vertices specified in a class of planar graphs. The first problem is concerned with enumerating minimal cutsets disconnecting two terminals in a class of undirected planar graphs, the second one is to enumerate minimal cutsets disconnecting more than two terminals in a class of undirected planar graphs, and the final problem is to enumerate minimal cutsets disconnecting source and sink specified in basically-series-parallel directed graphs. These problems are analyzed in a new cutset enumeration approach based on minimal-cutset-preserving graph reductions such that a graph defined in complex structure is transformed into a single edge by recursive applications of the mixture of the graph reductions. And some classes of planar graphs such as series-parallel or wheel graphs are identified for which such single edge reductions are possible. The approach is provided with a polynomial-time(measured in the size of a graph) enumeration algorithm which is illustrated with a numerical example. The cutset enumeration approach is a basic step in evaluating network reliabilities. It can also be applied to parametric max flow problems where edge capacities are not fixed but given as functions of parameters.