ENUMERATION OF ALL MINIMAL CUT-SETS FOR A NODE PAIR IN A GRAPH

被引：37

作者：

ARUNKUMAR, S ^{[1
]}

LEE, SH ^{[1
]}

机构：

[1] N CAROLINA STATE UNIV,DEPT ELECT ENGN,RALEIGH,NC 27650

来源：

IEEE TRANSACTIONS ON RELIABILITY | 1979年 / 28卷 / 01期

关键词：

Cut-sets; Graph; Implicit enumeration;

D O I：

10.1109/TR.1979.5220473

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents an efficient implicit enumeration algorithm for generating all minimal cut-sets separating a specified node pair in a connected graph. The arcs in the graph need not be directed. By stopping or branching at appropriate levels, the algorithm yields two connected subgraphs, each containing one of the nodes tobe separated, with the number of nodes in one of the subgraphs less than any specified value. Copyright © 1979 by The Institute of Electrical and Electronics Engineers, Inc.

引用

页码：51 / 55

页数：5

共 9 条

[1] CUT-SET GRAPH AND SYSTEMATIC GENERATION OF SEPARATING SETS [J].

ARIYOSHI, H .

IEEE TRANSACTIONS ON CIRCUIT THEORY, 1972, CT19 (03) :233-&

[2] IMPLICIT ENUMERATION SCHEME FOR PROPER CUT GENERATION [J].

BELLMORE, M ;

JENSEN, PA .

TECHNOMETRICS, 1970, 12 (04) :775-&

[3] DETERMINATION OF TIE SETS AND CUT SETS FOR A SYSTEM WITHOUT FEEDBACK [J].

BIEGEL, JE .

IEEE TRANSACTIONS ON RELIABILITY, 1977, 26 (01) :39-42

[4] NEW ALGORITHM FOR SYMBOLIC SYSTEM RELIABILITY ANALYSIS [J].

LIN, PM ;

LEON, BJ ;

HUANG, TC .

IEEE TRANSACTIONS ON RELIABILITY, 1976, 25 (01) :2-15

[5] GAUSSIAN ELIMINATION ALGORITHM FOR ENUMERATION OF CUT SETS IN A GRAPH [J].

MARTELLI, A .

JOURNAL OF THE ACM, 1976, 23 (01) :58-73

[6]

MARTELLI A, 1974, INFORMATION PROCESSI, P511

[7]

Mayeda W., 1972, GRAPH THEORY

[8] COMPUTER-PROGRAM FOR APPROXIMATING RELIABILITY CHARACTERISTICS OF ACYCLIC DIRECTED GRAPHS [J].

PEARSON, GDM .

IEEE TRANSACTIONS ON RELIABILITY, 1977, 26 (01) :32-38

[9] NEW TOPOLOGICAL FORMULA AND RAPID ALGORITHM FOR RELIABILITY ANALYSIS OF COMPLEX NETWORKS [J].

SATYANARAYANA, A ;

PRABHAKAR, A .

IEEE TRANSACTIONS ON RELIABILITY, 1978, 27 (02) :82-100

← 1 →