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.
본 논문은 플래너 그라프군에서 다음 세가지 경우에 대하여 그라프 축소 기법을 이용한 효율적인 최소절단집합 열거 (minimal cutset enumeration) 해법을 제시한다.
첫째, 무방향 플래너 그라프군에서 특정 두 마디 (vertex) 사이의 최소 절단집합의 열거 문제를 다룬다.
둘째, 무방향 플래너 그라프군에서 3개 이상의 특정 마디들 사이의 최소 절단집합의 열거 문제를 다룬다.
세째, 유방향 플래너 그라프군에서 특정 두 마디 (source와 sink) 사이의 최소절단집합의 열거 문제를 다룬다.
위의 각 경우에 대하여 최소절단집합 보존 (minimal-cutset-preserving) 그라프 축소 기법을 개발하고 이를 이용하여 최소절단집합을 보존하면서 복잡한 구조의 그라프가 단순 구조인 하나의 호 (edge) 로 축소가능한 그라프군의 성질을 규명한다. 규명된 그라프군을 대상으로 그라프 축소 기법에 근거한 효율적인 해법을 제시한다.
첫째 경우에서는 3가지 그라프축소 기법을 이용하여 series-parallel 그라프와 wheel 그라프가 축소가능 그라프군으로 규명되었다. 이 그라프들을 대상으로 계산복잡도가 마디 수의 제곱인 최소절단집합 열거 해법을 제시하였으며 또한 다른 연구에서 제시한 해법과 비교한 결과 월등히 효율적인 것으로 판명되었다.
둘째와 세째 경우에서는 각각 4가지와 3가지의 그라프 축소 기법을 이용하여 series-parallel 그라프가 축소가능 그라프군으로 규명되었으며 이 그라프군을 대상으로 각각 계산복잡도가 마디 수의 제곱인 최소절단집합 열거 해법을 제시하였다.
