THE MOST VITAL EDGES WITH RESPECT TO THE NUMBER OF SPANNING-TREES IN 2-TERMINAL SERIES-PARALLEL GRAPHS

被引：4
作者：
JAN, RH [1 ]
HSU, LH [1 ]
LEE, YY [1 ]
机构：
[1] NATL CHIAO TUNG UNIV,DEPT INFORMAT & COMP SCI,HSINCHU 30050,TAIWAN
来源：
BIT | 1992年 / 32卷 / 03期
关键词：
MOST VITAL EDGES; SPANNING TREES; 2-TERMINAL SERIES-PARALLEL GRAPHS;
D O I：
10.1007/BF02074877
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
A set E' of k edges in a multigraph G = (V, E) is said to be a k most vital edge set (k-MVE set) if these edges being removed from G, the resultant graph G' = (V,E - E') has minimum number of spanning trees. The problem of finding a k-MVE set for two-terminal series-parallel graphs is considered in this paper. We present an O(Absolute value of E) time algorithm for the case k = 1, and an O(Absolute value of V(k) + Absolute value of E) time algorithm for arbitrary k.
引用
收藏
页码：403 / 412
页数：10
相关论文
共 11 条
[1]  
AHO AV, 1974, DESIGN ANAL COMPUTER, P54
[2]   FINDING THE MOST VITAL ARCS IN A NETWORK [J].
BALL, MO ;
GOLDEN, BL ;
VOHRA, RV .
OPERATIONS RESEARCH LETTERS, 1989, 8 (02) :73-76
[3]  
COLBOURN CJ, 1987, COMBINATORICS NETWOR, P49
[4]  
Corley H. W., 1982, Operations Research Letters, V1, P157, DOI 10.1016/0167-6377(82)90020-7
[5]   TOPOLOGY OF SERIES-PARALLEL NETWORKS [J].
DUFFIN, RJ .
JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1965, 10 (02) :303-&
[6]  
Gould Ronald, 1988, GRAPH THEORY, pppl9X
[7]  
LUBORE SH, 1970, NAV RES LOG, V17, P497
[8]   ORDER-PICKING IN A RECTANGULAR WAREHOUSE - A SOLVABLE CASE OF THE TRAVELING SALESMAN PROBLEM [J].
RATLIFF, HD ;
ROSENTHAL, AS .
OPERATIONS RESEARCH, 1983, 31 (03) :507-521
[9]   THE RECOGNITION OF SERIES-PARALLEL DIGRAPHS [J].
VALDES, J ;
TARJAN, RE ;
LAWLER, EL .
SIAM JOURNAL ON COMPUTING, 1982, 11 (02) :298-313
[10]   STEINER TREES, PARTIAL 2-TREES, AND MINIMUM IFI NETWORKS [J].
WALD, JA ;
COLBOURN, CJ .
NETWORKS, 1983, 13 (02) :159-167
12